前言
Huffman Tree，有翻译成哈夫曼树，也有翻译成赫夫曼树的，其实都是一样的。哈夫曼树又称最优树，是一类带权路径长度最短的树。这里用最优二叉树来讨论。
最优二叉树（哈夫曼树）
上面说了“最优树是一类带权路径长度最短的树”。这里需要先了解三个概念：路径、路径长度、带权路径长度。
- 路径
两个结点之间的路线 - 路径长度
路径上的分指数就是路径长度 - 带权路径长度
- 结点的带权路径长度
每个结点都有自己的权重，而结点的带权路径长度是指路径长度乘以目的结点的权重 - 树的带权路径长度
树中所有叶子结点的带权路径长度之和
- 结点的带权路径长度
假设现在有4个结点[A, B, C, D]，它们组成的二叉树之中，树的带权路径长度最小的二叉树称为最优二叉树或者哈夫曼树。
上图的哈夫曼树的带权路径长度 = 2×3 + 4×3 + 5×2 + 7×1 = 35
构建哈夫曼树的一般算法如下：
1. 由给定的 n 个权值的结点去构建只有一个结点的二叉树，得到集合 F
2. 在 F 中选出权值最小和次小的树，它们分别作为左子树和右子树构建成一棵新的树，这个新的树的权值为它的左右孩子的权值之和
3. 从 F 中剔除选中的树，并将新的树放入 F
4. 重复步骤2、3，直到 F 中只剩一棵树，这棵树就是最优二叉树
哈夫曼编码
这是最优二叉树的一个经典应用，电报就应用了哈夫曼编码对报文进行了压缩、加密。
压缩报文
假设现在我们的所有对话可以用 A、B、C、D 涵盖，那么我们通过电报对话只需要约定好 A、B、C、D 的编码就好。我们通讯一般是用二进制串传输，称为二进制编码，那么我们应该如何给这四个字母定义编码呢？4转成二进制就是 100，显然如果每个字母对应的编码都是定长3的话，我们可以使用 0~3 的二进制来表示。
不过这里有个问题：我们说话时，每个字使用的频率是不同的，如果想要提高传输效率，那么要怎么压缩报文的长度呢？答案是将高频的字的编码设计得尽可能的短即可。不过这样就没有定长了，处理报文也变得麻烦了起来，要么就要增加结束标识（直接否掉，因为本来就是想尽量压缩报文，所以不想增加额外的标识）；要么就需要任意一个编码不能是另一个编码的前缀。
用上面的图作为例子，频率从高到低：A > B > C > D，可得以下表格
| 字母 | 编码 |
|---|---|
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
对比表格和图，是不是发现节点的带权路径长度和我们的结点的哈夫曼编码一致呢？结合前面提到的哈夫曼算法理解：权重越大的结点越靠前（在这个例子中，权重等价于使用频率）。
因为我们要使用二进制编码传输，所以只有 0 和 1。
加解密
上面的表格又可以称之为“密码本”，因为它记录着我们约定好的编码对应的字是什么，所以没有它，是很难暴力破解的。至于解密，因为每个编码都具有唯一性（每一个编码都不会是另一个编码的前缀），所以用程序做比较也是十分简单的，匹配成功就转成文字即可。
总结
使用哈夫曼编码的好处：
1. 对于高频词汇可以用更少的位表示，报文体积更小，发送更快（压缩）
2. 使用它加密，暴力破解难度大（前提是不能泄漏密码本）
3. 解密容易
4. 当密码本泄漏以后，可以通过更换密码本的方式保护尚未泄漏的信息，而更换密码本的成本十分低（不用修改代码）
