哈夫曼树

哈夫曼树实现思路：

形成分段式解决方案，把形成的N个树结构反复合并（两两合并）。每当两个树结构合并一次，就添加一个新的共享根节点

伪代码如下

if 森林结构中存在两个及以上彼此独立的树结构：
    选取两个分量最轻的树（根节点权值最低的）
    合并后放回原处，并且赋予其根节点新的加权值

示例：

哈夫曼树.jpg

上面出现出现的权重a,b,c,d,e,f,g,h,i字符出现的频次/概率/权重分别为：4、5、6、9、11、12、15、16、20。
各字符编码

a:0100
b:0101
c:1100
d:1101
e:011
f:100
g:101
h:111
i:00

WPL= 2 * 20 + 3 * （11+12+15+16）+ 4 *（4+5+6+9）= 298
如果用定长编码，9个字符需要4位进行存储，98 * 4 =392 （注：本来应该100，但教程上总和98，但不影响思路）

注意：

1. 前缀码：结构中任意有效编码不可能是其他编码的前缀
2. 其实，0代表的是左还是右，或者子数在左边还是右边不重要，他们的洗牌方式不会对解决方案最佳性产生影响（）
3. WPL：树的所有叶结点的带权路径长度之和，称为树的带权路径长度表示为WPL

哈夫曼编码

哈夫曼树的应用：在处理字符串序列时，如果对每个字符串采用相同的二进制位来表示，则称这种编码方式为定长编码。若允许对不同的字符采用不等长的二进制位进行表示，那么这种方式称为可变长编码。可变长编码其特点是对使用频率高的字符采用短编码，而对使用频率低的字符则采用长编码的方式。这样我们就可以减少数据的存储空间，从而起到压缩数据的效果。而通过哈夫曼树形成的哈夫曼编码是一种的有效的数据压缩编码。

示例如上

参考：

https://www.cnblogs.com/xidongyu/p/6031518.html