哈夫曼树
what
哈夫曼树是一颗最优二叉树，带权路径长度最小的二叉树，经常来用来进行数据压缩。
why
为什么这棵树是最优的？
一个棵树是不是最优的，要看它是否满足构建的这棵树的带权路径长度最小。
在证明哈夫曼树是一颗最优二叉树之前，要先知道这几个概念：
- 路径：从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径。
- 路径长度：从根节点开始计数到该节点，路径上的分支数目称作路径长度。
- 权：也称为权值，指的是节点的属性数值。
- 树的带权路径长度：树中所有叶子节点的带权路径长度之和，一般用WPL表示。
如上图中，a的权值为7，路径长度为1；b的权值为5，路径长度为2。
树的带权路径长度WPL=7x1+5x2+2x3+4x3=35
知道了这些，那为什么是最优的，知道构建的哈夫曼树，你就知道为什么了。
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
- 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
- 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
在上图中（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。
哈夫曼树在构建的过程中，将最短的路径，巧妙的给了权值最大的，最长的路径给了权值最小的，所以可使WPL最小。
为什么可以用来进行数据压缩（无损压缩）？
压缩不外乎就是对数据的编码处理，使其占用的内存更小。
在数据压缩中，有一种叫做无损压缩，它其中的原理利用了哈夫曼编码，哈夫曼编码相当于哈夫曼树理论的实践。
哈夫曼编码，是一种非常巧妙的编码方式，而且也是可变的，依据字符出现的概率来决定字符编码长度。
在编码时，首先根据待编码的文本统计出每个字符出现的概率，组成初始的节点。然后每次取出概率最小的两个节点，新建一个节点，使得新建节点的左右儿子为选取的两个节点，并且其概率是两个节点概率之和，把新建的节点再放进所有节点中重新选择最小的两个节点。重复此过程直到只剩一个节点，这个就是哈夫曼树的根节点。
以下以字符串"aaaaaabbbbccddd"为例进行说明，为了方便，以字符出现的频数来代替频率（实际中通常使用的是频率，二者效果上是一样的），经过统计，可以知道每个字符出现的频数为：
| a | b | c | d |
|---|---|---|---|
| 6 | 4 | 2 | 3 |
具体建树过程如下：
- 首先节点权值为6、4、2、3，选择最小的2和3，组成一个根节点为5的组合节点。
- 当前节点权值为6、4、5，选择最小的4和5，组成一个根节点为9的组合节点。
- 当前节点权值为6、9，选择最小的6和9，组成一个根节点为15的组合节点。
- 当前节点权值为15，只有一个节点，哈夫曼树建立完成。
![avatar]()
要从哈夫曼树得到每个字符的编码，只要在哈夫曼树中从根节点遍历到该字符节点，每次向左走时加一个0，向右走时加一个1，最终得到的字符串即为该字符的编码字符串。
如从上图可以看到，a的编码为0，b的编码为10，c的编码为110，d的编码为111。
哈夫曼编码之所以可以这样解码，是因为它是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀。于是给定一个编码后的串，其解码的结果是唯一的。
最终经过哈夫曼编码后为： 0 0 0 0 0 0 10 10 10 10 110 110 111 111 111 一共为31位，在原始的数据中，一个字符占用3bit, 一共需要45bit
一串字符串，经过哈夫曼编码从45bit压缩到了31bit。因为在这个过程没有数据的丢失，所以是无损压缩。