哈夫曼树介绍大家好，我是bigsai。原以为哈夫曼树和哈夫曼编码很难，结果很简单，老铁们！很多人可能听说过哈夫曼树和哈夫曼编码，但可能没有认真研究过。今天的文章是关于让我们更详细地谈谈哈夫曼树。首先，什么是哈夫曼树？哈夫曼树的定义：给定N个权值作为N个叶子节点，构造一棵二叉树。如果树的带权路径长度达到最小，这样的二叉树称为最优二叉树，也称为哈夫曼树（HuffmanTree），哈夫曼树是带权路径长度最短的树。权重越大的节点越靠近根。那么这棵树长什么样子呢？比如一开始由2、3、6、8、9个权重节点组成的哈夫曼树是这样的：从定义和图中也可以发现如下规律：初始节点都在树中叶节点上权重越大的节点离根越近。每个非叶节点都有两个子节点（因为我们是从下往上构建的，所以两个子节点构成了一棵新树的根节点）。大家可能很好奇这样的哈夫曼树是怎么构造出来的，其实是按照贪心的思想和规则构造出来的，而且构造出来的树的权重是最小的。下面将详细解释该规则。哈夫曼树中一个很重要的点：WPL（树的所有叶子节点的加权路径长度之和）。至于为什么按照哈夫曼树的方法得到的权值最小，这里就不证明了，只是从局部（三个节点）来看，权值较大的WPL在上层较低。WPL计算方法：WPL=sum(Wi*Li)其中Wi为第i个节点的权重（值）。Li是第i个节点的长度（深度）。比如上面由2、3、6、8、9个权重节点组成的哈夫曼树的WPL计算为（设根为第0层）：比如上面的哈夫曼树的WPL为：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61。既然了解了哈夫曼树的一些概念和WPL的计算方法，那我们就来看看哈夫曼树的具体构造方法吧！哈夫曼树的初始构造给出了一个有n个节点的森林。我们主要是利用贪心的思想来完成哈夫曼树的构建：在n个节点上找到两个权重最小的节点（根节点），为叶子结构构建一棵新树（根节点的权重为左节点和左节点的权重）rightchildrenand)先删除最小的两个节点（n-2），然后添加新的节点（n-1）重复上述操作，直到处理完所有节点。具体实现上，找到最小的两个节点需要进行排序操作，我们看一下形成一棵权重节点为2、6、8、9、3的哈夫曼树的过程。一开始，每个节点都是独立的，先对它们进行排序（这里使用优先队列），然后选择两个最小的节点（throwing）生成一个新的节点，然后加入到优先队列中。操作完成后，有节点5、6、8、9重复上述操作。这次末尾队列中有节点11、8、9（排序后的8、9、11）。如果队列为空，则返回该节点，这个节点就是整个哈夫曼树的根节点root。否则继续加入队列排序。重复上述操作，直到队列为空。在计算加权路径长度WPL时，需要重新计算高度（从下到上），因为哈夫曼树是自下而上构建的，高度不是保持一个常数。它可以构造然后计算。具体代码实际(仅供参考)importjava.util.ArrayDeque;importjava.util.ArrayList;importjava.util.Comparator;importjava.util.List;importjava.util.PriorityQueue;importjava.util.Queue;publicclassHuffmanTree{publicstaticclassnode{intvalue;nodeleft;noderight;intdeep;//记录深度publicnode(intvalue){this.value=value;this.deep=0;}publicnode(node1,noden2,intvalue){this.left=n1;this.right=n2;this.value=value;}}privatenoderoot;//最后生成的节点Listnodes;publicHuffmanTree(){this.nodes=null;}publicHuffmanTree(Listnodes){this.nodes=nodes;}publicvoidcreateTree(){Queueq1=newPriorityQueue(newComparator(){publicintcompare(nodeo1,nodeo2){returno1.value-o2.value;}});q1.addAll(nodes);while(!q1.isEmpty()){node1=q1.poll();node2=q1.poll();nodeparent=newnode(n1,n2,n1.value+n2.value);if(q1.isEmpty()){root=parent;return;}q1.add(parent);}}publicintgetweight(){Queueq1=newArrayDeque();q1.add(root);intweight=0;while(!q1.isEmpty()){nodeva=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;}}returnweight;}publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(newnode(2));list.add(newnode(3));list.add(newnode(6));list.add(newnode(8));list.add(newnode(9));HuffmanTreetree=newHuffmanTree();tree.nodes=list;tree.createTree();System.out.println(tree.getweight());}}outputresult:61HuffmanencodingexceptHuff你有听说过曼树，你可能听说过哈夫曼编码，但你可能不知道它是什么，哈夫曼编码其实是哈夫曼树的一个很重要的应用，这里简单介绍一下原理和哈夫曼编码的定义不是具体实现：哈夫曼编码（HuffmanCoding），又称哈夫曼编码，是一种编码方法，哈夫曼编码是一种可变字长编码（VLC）。霍夫曼在1952年提出了一种编码方法，这种方法完全根据字符出现的概率来构造不同前缀的平均长度最短的码字，有时称为最优编码，一般简称为霍夫曼编码（有时也称为Huff曼编码）。哈夫曼编码的目的是减少存储量。以一个连续的字符串为例，不考虑编程语言中的实际存储，以字符串aaaaaaaaaabbbbbcccdde为例。如果计算机中的每个字符都是固定长度存储的（假设二进制存储长度为4），计算机只知道0和1的二进制，假设a:0001b:0010c:0011d:0100e:0101，那么上面的字符串可以这样用二进制存储000100010001000100010001...0101如果每个字符如果编码长度相等，那么根本就没有存储空间优化，就是单个字符的长度*字符数。但是如果每个字符编码的长度不相等，那么设计的开放性就很强。比如字符串aaaaabb设计为01，b设计为1，那么二进制就是：010101010111如果a设计为1，b设计为01，那么二进制就是：111110101如果a设计为为1，b设计为0。那么二进制就是：1111100你看，在计算机的01二进制世界里，很明显，第二种优先于第一种，第三种优先于第二种.所以设计代码要考虑把出现的尽量短一些，出现少的稍长一些。但是，你需要考虑的一个问题是，二进制序列是从0、1、01、10、11开始的，如果001来了，是0、0、1还是0、01？所以当编码不等长时，你应该考虑这个编码必须是唯一的，不能有歧义。这个怎么做？简单，计算机只知道01二进制，二叉树就只有左右两个节点。对于一个字符，如果它对应的是一个叶子节点，那么可以直接判断，即如果这个值映射到一个二叉树，非叶子节点上不能存在字符。所以哈夫曼编码的具体过程就很清楚了。先统计字符出现的次数，然后用这个次数作为权值，按照上面介绍的方法构造一棵哈夫曼树。那么树的根就不存在了，左边是0右边是1。每个叶子节点得到的二进制数就是它的编码，这样出现频率高的字符就比较短，节省整个二进制存储的空间.结论哈夫曼树比较容易理解。主体结构采用贪心算法的思想自下而上搭建。相信看完哈夫曼编码你会有所收获。有兴趣的可以自己实现哈夫曼编码的代码(coding,decoding)。本人水平有限，如有错误，还望大家指正！
