哈夫曼树详解与构造
1介绍
定义：
-
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为
最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
简而言之，就是按照一个贪心思想和规则进行树的构造，而构造出来的这个树的权值最小！
其中WPL 表示计算出的权值。至于为什么按照哈夫曼树方法构造得到的权重最小。这里不进行证明。对于哈夫曼树，他的每个非叶子节点都有两个孩子 因为哈夫曼树的构造就是自底向上的构造 ，两两合并。
WPL计算方法:WPL=求和(wi li) 其中wi是第i个节点的权值(value)。li是第i个节点的长(深)度 .
1 哈夫曼树的构造
初始时候各个数值都是一个单节点森林！然后进行排序。
放入优先队列(自己排序也行)每次取两个最小权值顶点，构造父节点(value=left.value+right.value ).
-
如果
队列为空，那么返回节点，并且这个节点为根节点root。
-
否则继续加入队列进行排序。重复上述操作，直到队列为空。
在计算
带权路径长度的时候，需要重新计算树的高度(从下往上)，因为哈夫曼树是从下往上构造的，所以对于高度不太好维护，可以构造好然后计算高度。
比如上述的WPL 为：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61 .
3 代码实现
package 二叉树;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.PriorityQueue;import java.util.Queue;public class HuffmanTree {public static class node{int value; node left; node right;int deep;//记录深度public node(int value) {this.value=value;this.deep=0;}public node(node n1, node n2, int value) {this.left=n1;this.right=n2;this.value=value;}}private node root;//最后生成的根节点 List<node>nodes;public HuffmanTree() {this.nodes=null;}public HuffmanTree(List<node>nodes){this.nodes=nodes;}public void createTree() { Queue<node>q1=new PriorityQueue<node>(new Comparator<node>() {public int compare(node o1, node o2) {return o1.value-o2.value;}}); q1.addAll(nodes); while(!q1.isEmpty()) { node n1=q1.poll(); node n2=q1.poll(); node parent=new node(n1,n2,n1.value+n2.value); if(q1.isEmpty()) { root=parent;return; } q1.add(parent); }}public int getweight() { Queue<node>q1=new ArrayDeque<node>(); q1.add(root);int weight=0;while (!q1.isEmpty()) { node va=q1.poll();if(va.left!=null){ va.left.deep=va.deep+1;va.right.deep=va.deep+1; q1.add(va.left);q1.add(va.right);}else { weight+=va.deep*va.value;}}return weight;}public static void main(String[] args) { List<node>list=new ArrayList<node>(); list.add(new node(2)); list.add(new node(3)); list.add(new node(6)); list.add(new node(8));list.add(new node(9)); HuffmanTree tree=new HuffmanTree(); tree.nodes=list; tree.createTree(); System.out.println(tree.getweight());}}
哈夫曼树还是比较容易理解，主要构造利用贪心算法 的思想。代码实现复杂度可能不太高，如果有大佬指正还希望指正！
如果对数据结构，爬虫等感兴趣，还请关注我的公众号：bigsai .一起学习交流
长按识别
关注我们
转载是一种动力 分享是一种美德
