Huffman树的构造原理
Huffman树的来源
在编码过程中，人们需要尽可能的提高编码效率。例如，对于26个字母的编码，可以轻易地用五位二进制数来编码。然而，这样做会造成很大的空间浪费。于是不难想到，用1~5位二进制数来编码这26个字母。可是，这样的编码存在二义性。如，将a编码为0，b编码为01，c编码为00，d编码为1，对于“0001”这样一串编码，就存在多种解释。而Huffman发明的这个树完美地解决了问题。
Huffman树的构造原理
在一篇英语写成的文章中，每个字母有其各自的出现频率，若用一棵二叉树存储字母，我们希望出现频率较高的字母在二叉树上方，这样可以在遍历时效率更高。于是，我们在统计字母出现次数后，为字母分配相应的权值，权值较高的出现在二叉树上方。同时，二叉树的构造决定了它包含每个字母编码均不同。具体方法是，为每个左结点编码0，为每个右结点编码1，到达字母的0-1路径即组成了该字母的编码。
Huffman树的构造方法
给定一串权值由低到高的叶结点，每次取出两个结点，和已生成森林中无父结点的所有结点共同进行比较，并选出两个权值最小的结点，在森林中以较小结点为左结点，以较大结点为右结点，创建父结点，并将左右结点的权值之和赋予父结点，未进入森林的结点继续参与比较，直至森林形成一棵二叉树，该树即为Huffman树。
根据权值生成Huffman数的过程
给定权值: 2,3,5,7,11,13,17,19，则构造Huffman树的过程如下：
1.从权值中选择最小的2、3，此时森林为空，则由这两个结点生成父结点，并为其赋值为5。
2.继续从权值中选择最小的5、7，与森林中无父结点的5比较，则分别选择权值中的5和森林中的5，为父结点赋值10，权值7留下进行下次比较。
3.继续从权值中选出7、11，与10比较，选择最小的7与10作为左、右结点。
4.选择11、13，由于这两个权值均小于无父结点的权值17，则11和13在森林中创建一棵新树。
5.权值中最后的17、19，与无父结点的17、24比较，选择17与17作为左、右结点，构成Huffman树根的左节点，而19则与24作为右节点，至此，Huffman树构造完毕。
将每条左路径编码为0，右路径编码为1，则得到该权值下的编码规则。
在上图中，对权值2的编码即为遍历至2的路径：01110，这样容易得到所有的权值所对编码。由于每个权值的编码都由根结点出发生成，可知，即使每个权值编码长度不同，在译码过程中读至一特定序列，即可识别出该权值，进而判断该权值所对应的数据。