26考研——树与二叉树_树与二叉树的应用（5）

408答疑

三、树与二叉树的应用

哈夫曼树和哈夫曼编码

哈夫曼树的定义

概念

• 哈夫曼树是带权路径长度（WPL）​最小的二叉树，又称最优二叉树。
• ​权值：树中结点被赋予的表示特定意义的数值。
• ​叶结点的带权路径长度：叶结点到根结点的路径长度与该结点权值的乘积。
• ​树的带权路径长度（WPL）​：树中所有叶结点的带权路径长度之和，计算公式为：
  $$WPL=\sum _{i=1}^n{w}_i{l}_i$$
  其中，$w_i$ 为第 $i$ 个叶结点的权值，$l_i$ 为该叶结点到根结点的路径长度。

带权路径长度（WPL）计算

• 目标：构造 WPL 最小的二叉树（哈夫曼树）。
• ​路径长度：从根到某结点的路径上的边数（层数减1）。

示例分析

以下为三棵含4个叶结点（权值分别为7, 5, 2, 4）的二叉树及其 WPL 计算：

• ​二叉树(1)

  • 叶结点路径长度均为2
  • $WPL=7\times 2+5\times 2+2\times 2+4\times 2=36$

• ​二叉树(2)

  • 叶结点路径长度分别为2, 3, 3, 1
  • $WPL=4\times 2+7\times 3+5\times 3+2\times 1=46$

• ​二叉树(3)（哈夫曼树）

  • 叶结点路径长度分别为1, 2, 3, 3
  • $WPL=7\times 1+5\times 2+2\times 3+4\times 3=35$

结论：二叉树(3)的 WPL 最小，符合哈夫曼树的定义。

哈夫曼树的构造

算法描述

给定 $n$ 个权值分别为 $w_1,w_2,\dots ,w_n$ 的结点，构造Huffman树的算法描述如下：

1. 将这 $n$ 个结点分别作为 $n$ 棵仅含一个结点的二叉树，构成森林 $F$。
2. 构造一个新结点，从 $F$ 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从 $F$ 中删除刚才选出的两棵树，同时将新得到的树加入 $F$ 中。
4. 重复步骤 2 和 3，直至 $F$ 中只剩下一棵树为止。

哈夫曼树的性质

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了 $n-1$ 个结点（双分支结点），因此哈夫曼树的结点总数为 $2n-1$。
3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

示例

例如，权值 { 7 , 5 , 2 , 4 } \{7, 5, 2, 4\} {7,5,2,4} 的哈夫曼树的构造过程如下图所示：

• (1) 初始状态，权值分别为 7, 5, 2, 4。
• (2) 第一次合并，将权值 2 和 4 的结点合并，新结点权值为 6。
• (3) 第二次合并，将权值 5 和 6 的结点合并，新结点权值为 11。
• (4) 最终态，最终哈夫曼树的权值为 18。

通过这个过程，可以验证下图(4)树的带权路径长度 (WPL) 最小，因此它恰好为哈夫曼树。

哈夫曼编码

Huffman树的编码规则

• Huffman树的左树编码为0，右树编码为1，则每一个叶子结点将得到唯一的编码，即为Huffman编码。

Huffman树的构建过程

1. 先以字符串中每个字符出现的次数为权值构建Huffman树。
2. 从根结点开始对分支进行编码，左分支为0，右分支为1。
3. 所有权值结点都在叶子结点位置，遍历从根到叶子结点的每条路径，将获得对应字符的Huffman编码。

前缀编码

• 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
• 对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原字符，再对剩余的码串执行同样的解码操作。
• 例如，码串 0010110 可被唯一地翻译为 A, A, B 和 C。另举反例：若再将字符 D 的编码设计为 11，此时 11 是 110 的前缀，则上述码串的后三位就无法唯一翻译。

前缀编码的分析及应用

• Huffman编码可以利用二叉树来设计二进制前缀编码。假设为 A, B, C, D 四个字符设计前缀编码，可以用下图所示的二叉树来表示，4 个叶结点分别表示 4 个字符，且约定左分支表示 0，右分支表示 1，从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码，可以证明如此得到的必为前缀编码。由下图得到字符 A, B, C, D 的前缀编码分别为 0, 10, 110, 111。

Huffman树的构造及相关的分析

压缩原理

• 在未压缩之前一个字符占一个字节，现在对字符进行二进制编码之后，一个字节8个比特位列现在可以表示多个字符，所以说一次压缩，就会节省很多字节，也就起到了压缩的作用。
• Huffman编码是一种非常有效的数据压缩编码。由Huffman树得到Huffman编码是很自然的过程。首先，将每个字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的Huffman树。然后，将从根到叶结点的路径上分支标记的字符串作为该字符的编码。

示例分析

• 例如，下图所示为一个由Huffman树构造Huffman编码的示例，矩形方块表示字符及其出现的次数。这棵哈夫曼树的 WPL 为 $WPL=1\times 45+3\times (13+12+16)+4\times (5+9)=224$。此处的 WPL 可视为最终编码得到二进制编码的长度，共 224 位。若采用 3 位固定长度编码，则得到的二进制编码长度为 300 位，因此 Huffman编码共压缩了 25% 的数据。利用 Huffman树可以设计出总长度最短的二进制前缀编码。

注意事项

• 左分支和右分支究竟是表示 0 还是表示 1 没有明确规定，因此构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且为最优。

并查集（略）

四、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书