1、哈夫曼树的定义和原理
在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为
式中，wi 是第i个叶结点所带的权值，li 是该叶结点到根结点的路径长度。
在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。例如，下图中的3棵二叉树都有4个叶子结点a, b,c,d,分别带权7,5,2,4，它们的带权路径长度分别为
a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
其中，图c树的WPL最小。可以验证，它恰好为哈夫曼树。
2、哈夫曼树的构造
步骤：
- 先把有权值的叶子结点按照从大到小（从小到大也可以）的顺序排列成一个有序序列。
- 取最后两个最小权值的结点作为一个新节点的两个子结点，注意相对较小的是左孩子。
- 用第2步构造的新结点替掉它的两个子节点，插入有序序列中，保持从大到小排列。
- 重复步骤2到步骤3，直到根节点出现。
看图就清晰了，如下图所示：
3、哈夫曼编码
赫夫曼当前研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。
哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
比如我们有一段文字内容为“ BADCADFEED”要网络传输给别人，显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如下表所示：
这样按照固定长度编码编码后就是“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的。
假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。
下图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。
这棵哈夫曼树的WPL为:
WPL = 2 ∗ ( 15 + 27 + 30 ) + 3 ∗ 15 + 4 ∗ ( 5 + 8 ) = 241 WPL=2*(15+27+30) + 315 + 4(5+8)=241WPL=2∗(15+27+30)+3∗15+4∗(5+8)=241
此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如下表所示这样的定义。
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
我们将文字内容为“ BADCADFEED”再次编码，对比可以看到结果串变小了。
- 原编码二进制串: 000011000011101100100011 (共 30个字符)
- 新编码二进制串: 10100101010111100(共25个字符)
也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。
注意:
0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必然相同且是最优的。
————————————————
原文链接：https://blog.csdn.net/Real_Fool_/article/details/113930623