核心概念与定义

哈夫曼树（Huffman Tree），又称最优二叉树，是在含有 nn 个带权叶子节点的二叉树中，带权路径长度（WPL）最小的二叉树。

  • 路径：从树中的一个节点到另一个节点所经过的分支序列。
  • 路径长度：路径中包含的分支数。
  • 节点的带权路径长度：从根节点到该节点的路径长度与节点权值的乘积。
  • 树的带权路径长度（WPL）：所有叶子节点的带权路径长度之和。
WPL=∑i=1nwi×liWPL = \sum_{i=1}^{n} w_i \times l_i

其中，wiw_i 表示第 ii 个叶子节点的权值，lil_i 表示该叶子节点到根节点的路径长度。

树的加权平均路径长度为：

WPL∑i=1nwi\frac{WPL}{\sum_{i=1}^{n} w_i}

哈夫曼树的 WPL 也等于树中所有分支节点（非叶子节点）的权值之和。

构建步骤

哈夫曼树采用贪心策略：每次选择当前权值最小的两个节点进行合并。

假设有 nn 个权值，构造步骤如下：

  1. 初始化森林：将 nn 个权值分别作为 nn 棵仅含根节点的二叉树，组成一个森林。
  2. 选择最小节点：在森林中选出根节点权值最小的两棵树，作为新树的左右子树。
  3. 生成新节点：新树根节点的权值等于两棵子树根节点权值之和。
  4. 更新森林：从森林中删除刚才选出的两棵树，并加入新生成的树。
  5. 重复合并：重复步骤 2～4，直到森林中只剩一棵树，这棵树就是哈夫曼树。

实例演示

给定一组权值：[5, 9, 12, 13]。

  1. 合并最小的 5 和 9，生成节点 14；森林变为 [12, 13, 14]。
  2. 合并最小的 12 和 13，生成节点 25；森林变为 [14, 25]。
  3. 合并 14 和 25，生成根节点 39，构建完成。

本例的带权路径长度为：

WPL=14+25+39=78WPL = 14 + 25 + 39 = 78

也可以根据叶子节点的深度计算：

WPL=5×2+9×2+12×2+13×2=78WPL = 5 \times 2 + 9 \times 2 + 12 \times 2 + 13 \times 2 = 78

重要性质

性质 说明
严格正则二叉树 哈夫曼树不存在度为 1 的节点，只有度为 0 的叶子节点和度为 2 的分支节点，因此它是一棵严格正则二叉树（也称严格二叉树）。
节点总数为 2n−12n-1 若有 nn 个叶子节点，构建过程中会产生 n−1n-1 个分支节点，因此节点总数为 2n−12n-1。
权值越大，通常越靠近根节点 权值较大的节点具有更短的路径，权值较小的节点具有更长的路径，从而使 WPL 最小。
结构可能不唯一 当存在相同权值时，不同的选择顺序或左右子树安排可能得到不同结构，但最小 WPL 相同。

重点：哈夫曼树一定是严格正则二叉树，即每个分支节点都有且仅有两个子节点。

哈夫曼编码

定长编码与变长编码

  • 定长编码：每个字符使用相同长度的二进制位表示。
  • 变长编码：不同字符使用不同长度的二进制位表示。

定长编码所有节点都在同一层

为了压缩数据，变长编码通常让出现频率高的字符使用较短编码，让出现频率低的字符使用较长编码，从而降低字符的平均编码长度。

前缀编码

如果一个编码集合中，任何一个编码都不是其他编码的前缀，则称其为前缀编码。

例如，为字符分配以下编码：

字符 编码
A 0
B 10
C 110

这组编码满足前缀编码的要求。从左向右扫描码串，只要识别出一个有效编码，就能立即确定对应字符。例如：

0010110 = 0 | 0 | 10 | 110 = AABC

如果再给字符 D 分配编码 11，那么 11 就会成为 110 的前缀。此时码串末尾的 110 既可以解释成 C，也可以解释成 DA，从而失去唯一可译性。

使用二叉树生成前缀编码

可以通过二叉树设计二进制前缀编码：

  • 每个叶子节点对应一个字符；
  • 左分支标记为 0，右分支标记为 1；
  • 从根节点到叶子节点路径上的 0/1 序列，就是该字符的编码。

例如：

A = 0
B = 10
C = 110
D = 111

由于字符只出现在叶子节点，一个字符对应的路径不可能是另一字符路径的前缀，因此生成的编码一定是前缀编码。

哈夫曼编码示例

哈夫曼编码是一种高效的无损数据压缩编码。构建方法如下：

  1. 将每个字符作为独立的叶子节点，字符出现的频率（或次数）作为权值。
  2. 根据这些权值构建哈夫曼树。
  3. 约定左分支为 0、右分支为 1。
  4. 将根节点到各叶子节点路径上的分支标记依次连接，得到对应字符的编码。

假设共有 100 个字符，各字符出现次数如下：

字符 出现次数 哈夫曼编码 编码长度
a 45 0 1
b 13 101 3
c 12 100 3
d 16 111 3
e 9 1101 4
f 5 1100 4

对应的合并过程为：

5 + 9   = 14
12 + 13 = 25
14 + 16 = 30
25 + 30 = 55
45 + 55 = 100

该哈夫曼树的 WPL 为：

WPL=1×45+3×(13+12+16)+4×(5+9)=224WPL = 1 \times 45 + 3 \times (13 + 12 + 16) + 4 \times (5 + 9) = 224

这里的 WPL 表示对这 100 个字符编码后，二进制码串的总长度为 224 位。

若使用定长编码，6 种不同字符至少需要 3 位二进制数表示，因此总长度为：

3×100=300 位3 \times 100 = 300\text{ 位}

与定长编码相比，哈夫曼编码节省了 300−224=76300-224=76 位，压缩率约为：

300−224300×100%≈25.3%\frac{300-224}{300} \times 100\% \approx 25.3\%

因此，哈夫曼树能够生成总长度最短的二进制前缀编码。

左右分支分别使用 0 还是 1 并无强制规定；当存在相同权值时，不同的合并顺序也可能得到形态不同的哈夫曼树。但这些树的 WPL 相同，最优性不受影响。

周六了还在忙活着，又是过了12点。
要是能休息一天就好了，但休息了也没事干。
只能来点可爱的图片放松下了🥹
牢广