Ⅰ 前言
在前面的文章里，我详细讲解了树与二叉树。这篇文章，我们就来看一看二叉树的一种情况——最优二叉树，也称哈夫曼树（Huffman Tree）。
对二叉树这个数据结构还不完全清楚的同学可以跳转去下面的文章。
Ⅱ 什么是哈夫曼树
在前面我们说了，哈夫曼树是二叉树的一种，那到底是什么是哈夫曼树呢？这里我给出一个定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
完全不知道这个定义在说什么。
不要急，我们慢慢来。
首先来看几个概念。
- 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。比如从根节点到 a ，就是一条路径。
- 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。比如根节点到 c 和 d 都是 3。
- 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。比如 b 的权是 5。
- 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。比如 b 带权路径长度 = 2 * 5 = 10
- 树的带权路径长度：指树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。比如下图中的树的带权路径长度 WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 36。
所以，当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，也叫“哈夫曼树”。
在构建哈夫曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。
有了这个概念，我们就可以开始构建哈夫曼树了。
Ⅲ 哈夫曼树的生成及哈夫曼编码
在构建哈夫曼树之前，我们先要知道什么是哈夫曼压缩。
压缩算法有很多种，哈夫曼压缩是一种频度压缩。我举一个例子。
假设一个文本文件全部由英文字母构成，那么哈夫曼压缩就是将出现次数(频度)最高的字母用最短的编码来表示。ASCII码占1byte，即8bit，那么将其用2bit的编码来取代，则每个字符会节省6bit的空间。
哈夫曼压缩对应的就是哈夫曼编码，而哈夫曼编码就需要通过哈夫曼树来生成。现在我们来走一遍这个哈夫曼树生成以及哈夫曼编码构建的过程。
A. 构造哈夫曼树
我用一个字符串当作例子来构造一棵哈夫曼树。
egeaefebaeeauefffeeffeebe
a. 频度统计
要构造一棵哈夫曼树，我们需要先知道每个字符的频度。
| 字符 | 频度 |
|---|---|
| a | 3 |
| b | 2 |
| e | 12 |
| f | 6 |
| g | 1 |
| u | 1 |
b. 生成哈夫曼树
我们需要找到最小频度的节点，然后生成新节点，生成过程如下?
第一步
第二步
第三步
第四步
第五步
这样，一棵哈夫曼树就构造完成了。
B. 哈夫曼编码
上一步我们构造出了一棵哈夫曼树，根据这棵树我们现在进行编码。
首先，我们对方向编码，可以向左是0向右是1，也可以反过来，这只是一个编码规则。我定为向左为0.
接下来就是从根节点沿着这棵树编码。
比如e,从根节点向左一次就到了，所以e的编码为：0
同样的，比如f,需要从根节点先向右，再向左，所以f的编码是：10
按照以上规律，我们可以写出哈夫曼编码
| 字符 | 编码 |
|---|---|
| a | 110 |
| b | 1110 |
| e | 0 |
| f | 10 |
| g | 11110 |
| u | 11111 |
所以egeaefebaeeauefffeeffeebe转化成哈夫曼编码为：
011110011001001110110001101111101010100010100011100
哈夫曼编码完成。
C. 解码
解码依旧是根据构造的哈夫曼树，以及你制定的编码规则。
011110011001001110110001101111101010100010100011100
根据这个编码，我做几个解码。
从根节点，先向左，到了e，所以第一个是e，然后回到根节点。
向右，向右，向右，向右，向左，到了g，所以第二个是g，再回到根节点。
根据这个规律，按照之前构造的哈夫曼树还原出这串字符串。
这就是解码的实现。
Ⅳ 总结
哈夫曼编码其实在生活中非常常用到，因为它的压缩率比较高，而且丢包率也很低。
这篇文章只是作为一个引子，简单讲述了哈夫曼编码的生成原理以及思想，下面的两篇文章就是实战了，我们将用哈夫曼编码的思想，实现一个真正可以压缩解压缩文件的程序，大家若有兴趣可以来看一看，自己动手和我一起实现一个有意思的程序。