【数据结构与算法】哈夫曼树与哈夫曼编码

哈夫曼树（最优二叉树）

在介绍哈夫曼树之前，我们需要介绍一些概念：

• 路径：路径是指从一个结点到另一个结点的之间所经过的所有结点构成的序列。

• 路径长度：路径长度是路径上所经过的边的个数

• 权：在应用树的时候，我们常常会将树的结点赋予一个表示某种意义的数值，这个值称为权。

• 结点的带权路径长度：从根结点到一个结点的路径长度 * 该结点的权值 = 该结点的带权路径长度。

• 树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和称为树的带权路径长度

定义

在含有n个带权叶结点的二叉树中，其中带权路径最小的二叉树称为哈夫曼树，也称最优二叉树。

举个🌰（WPL的计算）

第一棵树的 $WPL=7\ast 2+5\ast 2+2\ast 2+4\ast 2=36$

第二棵树的 $WPL=4\ast 2+7\ast 3+5\ast 3+2\ast 1=46$

第三棵树的 $WPL=7\ast 1+5\ast 2+2\ast 3+4\ast 3=35$

第三颗树的 WPL 恰好是所有含有n个带权叶结点的二叉树中最小的，因此第三棵树为哈夫曼树。

注意：证明一个树是否为哈夫曼树，要看的是所有含有n个带权叶结点的WPL，而不是给几个二叉树选其中WPL最小的。（当然，由于这种证明几乎不可能实现，所以要证明一棵树为哈夫曼树，我们只需要证明它的结构符合最优构造方法即可——因为哈夫曼树并不唯一，例如把一颗哈夫曼树的左右子树交换，它就构成了一棵新的哈夫曼树）。

哈夫曼树的构造（最优二叉树的构造）

给定 $n$ 个权值分别为 $w_1,w_2,...,w_n$ 的结点，构造最优二叉树的方法如下：

1. 将这 $n$ 个结点视为 $n$ 棵只有一个结点的二叉树，它们构成了一个森林$F$。
2. 在森林中选择两颗根节点权值最小的二叉树 $T_1,T_2$，新增一个结点 $N$，把 $T_1,T_2$ 的根节点作为 $N$ 的左、右孩子构成一棵新的二叉树 $T_3$，$N$的权值等于$T_1,T_2$的根的权值之和。
3. 从 $F$ 中删除 $T_1,T_2$，把 $T_3$加入到 $F$ 中。
4. 重复步骤 $2,3$，直到 $F$ 中只剩下一颗树。

如果对哈夫曼树的构造方法的正确性感兴趣的同学，可以搜一搜哈夫曼树的构造方法的正确性证明。

举个🌰

把这几个叶结点按权值的从小到大排列，有：

选择权值最小的两个结点构成新的二叉树，有：

继续选择两个最小的结点，有：

继续：

这样我们就得到一颗哈夫曼树了

哈夫曼编码

在了解哈夫曼编码前，我们先了解一些相关的概念：

• 定长编码：长度固定的编码。
• 变长编码：长度不固定的编码。
• 前缀编码：没有一个编码是另一个编码的前缀，这样的编码叫做前缀编码（显然，根据定义来说，定长编码一定是前缀编码，变长编码不一定是前缀编码）。

对于前缀编码来说，我们可以用树辅助构造前缀编码。

例如：假设要为a，b，c，d四个字符设计二进制前缀编码，那么我们可以用二叉树来辅助构造。

为了使编码能够符合前缀编码的要求，显然，a、b、c、d不会出现在分支结点上。

我们设从任意结点往左边走代表0，从任意结点往右边走代表1，（即指向左子树的边代表0，指向右子树的边代表1）那么a、b、c、d的编码为从根节点到对应叶结点所经过的边代表的值的序列。

我们可以得到如下所示的二叉树：

• a的编码为：0
• b的编码为：10
• c的编码为：110
• d的编码为：111

显然，没有一个编码是另一个编码的前缀，这种编码是前缀编码。

定义

哈夫曼编码是一种变长的二进制前缀编码，它利用哈夫曼树来辅助构造编码，能够非常有效地压缩二进制数据。

构造

我们将每一个字符当做一个独立的结点，其权值等于它出现的次数（或频度），构造一棵哈夫曼树。

设从任意结点指向左子树的边代表0，指向右子树的边代表1或指向左子树的边表示1，指向右子树的边表示0。则各个结点的编码为从根节点到对应结点所经过的边代表的值的序列。

上面的例子就是一个构造哈夫曼编码的案例。

注意：相同结点构造出的哈夫曼树并不唯一，因为它并没有限制到底是左大右小还是右大左小。但相同结点构造出的不同的哈夫曼树的WPL一定是相同的。

同理，哈夫曼编码也是不唯一的。

全篇至此结束，感谢观看。