哈夫曼树
哈夫曼树（Huffman Tree）
树的每一个结点都可以拥有自己的权值（weight），假设二叉树有n个叶子结点，每个叶子结点都带有权值，从根结点到每个叶子结点的长度为，则树的带权路径长度（WPL, Weighted Path Length）为：
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明的，哈夫曼树是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。
例如，有五个叶子结点，它们的权值为{1, 2, 3, 4, 5}，用此权值序列可以构造出形状不同的多个二叉树。
WPL = 21
WPL = 45
WPL = 9
怎样才能保证构建出的二叉树带权路径长度最小呢？原则上，应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一棵。
哈夫曼树的构造
哈夫曼树的构造方法就是每次把权值最小的两棵二叉树合并。
例如有6个叶子结点，权重依次是2、3、7、9、18、25。
第一步：把每一个叶子结点都当成一棵独立的树（只有根结点的树），这样就形成了一个森林。
哈夫曼森林：合并最小的两棵树
解锁完整互动实验、进阶解析与精选参考答案。
第二步：从森林中移除权值最小的两个结点，生成父结点，父结点的权值是这两个结点权值之和，把父结点加入森林。重复该步骤，直到森林中只有一棵树为止。
哈夫曼树有以下几个特点：
-
没有度为1的结点。
-
哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树。
-
对同一组权值，可能存在不同构的两棵哈夫曼树。
知识测验
哈夫曼编码（Huffman Code）
哈夫曼编码是一种高效的编码方式，在信息存储和传输过程中用于对信息进行压缩。要理解哈夫曼编码，需要从信息存储的底层逻辑讲起。
计算机不是人，它不认识中文和英文，更不认识图片和视频，它唯一认识的就是0（低电平）和1（高电平）。因此，计算机上一切文字、图像、音频、视频，底层都是用二进制来存储和传输的。
将信息转换成计算机能够识别的二进制形式的过程被称为编码。ASCII码使用7位编码，存储时常以8位字节表示。例如字符串APPLE表示成8位二进制编码为01000001 01010000 01010000 01001100 01000101。
显然，ASCII码是一种等长编码，也就是任何字符的编码长度都相等。等长编码的优点明显，因为每个字符对应的二进制编码长度相等，所以很容易设计，也很方便读写。但是计算机的存储空间以及网络传输的带宽是有限的，等长编码最大的缺点就是编码结果太长，会占用过多资源。
使用不等长编码，让出现频率高的字符用的编码短一些，出现频率低的字符编码长一些，可以使编码的总长度减小。但是不等长编码是不能随意设计的，如果一个字符的编码恰好是另一个字符编码的前缀，就会产生歧义的问题。
哈夫曼编码就是一种不等长的编码，并且任何一个字符的编码都不是另一个字符编码的前缀，因此可以无二义地进行解码，并且信息编码的总长度最小。
哈夫曼编码并非一套固定的编码，而是根据给定信息中各个字符出现的频次，动态生成最优的编码。哈夫曼编码的生成过程就用到了哈夫曼树。
例如一段信息里只有A、B、C、D、E、F这6个字符，出现的次数分别是2次、3次、7次、9次、18次、25次。通过把这6个字符当成6个叶子结点，将出现次数作为结点的权重，生成一棵哈夫曼树。将哈夫曼树中结点的左分支当做0、结点的右分支当做1，从哈夫曼树的根结点到每一个叶子结点的路径，都可以等价为一段二进制编码。
沿树读取哈夫曼编码
解锁完整互动实验、进阶解析与精选参考答案。
| 字符 | 编码 |
|---|---|
| A | 11100 |
| B | 11101 |
| C | 1111 |
| D | 110 |
| E | 10 |
| F | 0 |
因为每一个字符对应的都是哈夫曼树的叶子结点，从根结点到这些叶子结点的路径并没有包含关系，最终得到的二进制编码自然也不会是彼此的前缀。
知识测验
为四个字符构造前缀码
字符A、B、C、D的频次为1、2、4、8。每次合并当前最小的两棵树，把较小权重放左边；画出合并过程，左边标0、右边标1，写出编码和WPL。与每字符2位的等长编码比较总位数。