【数据结构】哈夫曼树和哈夫曼编码

一、哈夫曼树

1.1 哈夫曼树的概念

给定一个序列，将序列中的所有元素作为叶子节点构建一棵二叉树，并使这棵树的带权路径长度最小，那么我们就得到了一棵哈夫曼树（又称最优二叉树）

接下来是名词解释：

• 权：节点的数值
• 路径长度：两节点间路径的边数
• 带权路径长度：节点的权值乘以该节点到根节点的路径长度即为该节点的带权路径长度。哈夫曼树的带权路径长度是树中所有叶子节点的带权路径长度之和。

例如下面这棵哈夫曼树：

通过观察我们可以发现，所有父节点的权值都是自身的两个子节点的权值之和。而为了要使树的带权路径长度最小，我们要尽可能的让权值小的节点离根节点远，让权值大的节点离根节点近。

因此，我们引出哈夫曼树的构造算法。

1.2 哈夫曼树的构造算法

要将一个序列构造成一棵哈夫曼树，我们首先需要对其进行升序排序

将排序好后的序列中的每个值看作一棵只有一个节点的树，从中选出根节点权值最小的两棵树作为新树的左右子树，并将这两棵树从序列中删除，而新树的根节点的权值是这两棵树根节点的权值之和

哈夫曼树没有规定左右子树的顺序，因此下面的例子中将10和18的位置对调也是正确的

将新树的根节点的权值放入序列中并重新进行升序排序，重复上述步骤

至此，就构建了一棵哈夫曼树

因为哈夫曼树没有规定左右子树的顺序，因此一个序列可以构建出不同的哈夫曼树

二、哈夫曼编码

2.1 等长编码

假设我们要对一个字符串ABAACDC进行二进制编码

我们可以按顺序给每个字符设置一个编码，A为0，B为1，C为10，D为11

那么就可以将上面的字符串转化为0100101110

但是在解码的时候我们会发现，这一串二进制序列可以解码为ACACDBA、ACABABDA等字符串，出现了歧义。

这是因为我们在对字符进行编码的时候，出现了一个字符是另一个字符的前缀的情况，例如D可以用两个B来表示。

为了避免歧义，我们可以采用等长编码的方案，就是每个字符的编码都一样长，例如A为00，B为01，C为10，D为11，这样就不会产生歧义了。

但是这种方案并不是一个最短的方案。

2.2 哈夫曼编码

统计字符出现的次数，把字符定义成一个节点，节点的权值就是它出现的次数。

例如上面A出现了3次，B出现了1次，C出现了2次，D出现了1次

哈夫曼编码的核心思想就是让出现次数越多的字符编出来的码越短，我们将全部节点构建成一棵哈夫曼树，出现次数越少的字符对应的节点就越靠近树的底层，编码也就越长，出现次数越多的字符编码就越短。

对二叉树的边标号，向左的边标为0，向右的边标为1，至此所有字符的编码就是从根节点到该字符节点路径上经过的标号，例如A为1，B为010，C为00，D为011，这种编码方案就叫做哈夫曼编码。

构建哈夫曼树的时候，所有的字符节点都是叶子节点，不会出现一个字符出现在另一个字符的路径上，也就不会出现一个字符是另一个字符的前缀这种造成歧义的情况

哈夫曼树的编码不是唯一的，节点放置的左右也会造成字符编码的不同，但是生成的编码长度一定都是一样的。

完.