跳转至

408 高频考点精讲 01:哈夫曼树(Huffman Tree)

模块归属:数据结构 · 树结构
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:6 次(2016~2025 年:2018#5、2019#3、2021#5、2022#5、2023#4、2025#5)
  • 历年总考查频次:9 次(含 2010#6、2012#41 大题、2015#3)
  • 出题形式:单项选择题为主,曾命制过综合解答题(2012 年第 41 题,分值 10 分)
  • 命题特点:
  • 考频稳定,平均 1~2 年考查一次。
  • 题型覆盖:带权路径长度(WPL)计算、加权平均码长、特定码长字符计数、树节点代数推导、编码树结构辨析。
近十年考查年份分布:
2016  2017  2018   2019   2020   2021   2022   2023   2024   2025
 -     -     √      √      -      √      √      √      -      √
            (#5)   (#3)          (#5)   (#5)   (#4)          (#5)

二、 具体考察内容

1. 核心定义及构造规则

  • 哈夫曼树(最优二叉树):给定 \(n\)$ \text{个权值作为} $\(n\) 个叶子节点,构造一棵二叉树,使其带权路径长度(WPL)达到最小。
  • 构造算法步骤:
  • 将 \(n\)$ \text{个权值分别作为单节点二叉树,构成集合} $\(F\);
  • 选出两棵根节点权值最小的树,作为左右子树合并为新二叉树,新二叉树根节点权值为二者之和;
  • 从 \(F\)$ \text{中删除选出的两棵树,并将新树放入} $\(F\);
  • 重复上述步骤,直到 \(F\) 中仅剩一棵树。

2. 核心定理推导

  1. 严格二叉树性质:
  2. 哈夫曼树不存在度为 1 的节点(\(n_1 = 0\))。
  3. 仅存在度为 0 的叶子节点(\(n_0\)$ \text{)及度为 2 的分支节点(} $\(n_2\))。
  4. 根据二叉树性质 \(n_0 = n_2 + 1\),推导得出: $$ \text{总节点数 } n = n_0 + n_1 + n_2 = 2n_0 - 1 $$ $$ \text{分支节点数 } n_2 = n_0 - 1 $$
  5. 若编码字符数为 \(n\)$ \text{(叶子数),则整棵树共有} $\(2n - 1\)$ \text{个节点,共执行} $\(n - 1\) 次两两合并。
  6. 唯一性辨析:
  7. 左右子树位置可互换,且存在同权节点时形态不唯一。
  8. 最小带权路径长度(WPL)数值唯一。

3. WPL 计算及加权平均码长

  • 定义式:\(\text{WPL} = \sum_{i=1}^n w_i \times l_i\) (\(w_i\)$ \text{为权值,} $\(l_i\) 为根到叶节点的路径分支数)。
  • 快速计算方法(非叶节点累加法): $$ \text{WPL} = \sum \text{所有分支节点权值} $$ 原理:每次合并生成的分支节点权值,均被其子树各叶子节点各计入一次路径。
  • 加权平均码长: $\(\bar{L} = \frac{\text{WPL}}{\sum w_i} = \frac{\sum (w_i \times l_i)}{\sum w_i}\)$

4. 前缀编码及定长编码对比

  • 前缀编码:任意字符编码均不是其他字符编码的前缀。二叉树中各字符必须全部位于叶子节点。
  • 定长编码:每个字符编码位数相同,对应二叉树中所有叶子节点深度均相等(处于同一层)。
  • 哈夫曼编码:变长前缀编码,高频字符靠近根节点(码长短),低频字符远离根节点(码长长),各字符不要求在同一层。

三、 近十年真题精讲(2016~2025)


【真题 1】2025 年 408 第 5 题 · 编码长度统计

题目
设字符集 \(S\) 包含 7 个字符,各字符出现的频次分别是 2, 3, 4, 6, 8, 10, 11。
为 \(S\) 中的各字符构造哈夫曼编码,编码长度不小于 3 的字符个数是( )。
A. 2          B. 3          C. 4          D. 5

【解析】

  1. 合并过程(频次排序:2, 3, 4, 6, 8, 10, 11):
  2. 合并 2, 3 \(\to\) 新节点 5,序列变为:4, 5, 6, 8, 10, 11
  3. 合并 4, 5 \(\to\) 新节点 9,序列变为:6, 8, 9, 10, 11
  4. 合并 6, 8 \(\to\) 新节点 14,序列变为:9, 10, 11, 14
  5. 合并 9, 10 \(\to\) 新节点 19,序列变为:11, 14, 19
  6. 合并 11, 14 \(\to\) 新节点 25,序列变为:19, 25
  7. 合并 19, 25 \(\to\) 根节点 44
  8. 树形结构:
               44 (根,深度0)
             /    \
           19      25 (深度1)
          /  \    /  \
         9   10  11   14 (深度2)
        / \          /  \
       4   5        6    8 (深度3)
          / \
         2   3 (深度4)
    
  9. 统计码长(即叶节点深度):
  10. 字符 10:深度 2,码长 2
  11. 字符 11:深度 2,码长 2
  12. 字符 4:深度 3,码长 3
  13. 字符 6:深度 3,码长 3
  14. 字符 8:深度 3,码长 3
  15. 字符 2:深度 4,码长 4
  16. 字符 3:深度 4,码长 4
  17. 编码长度 \(\ge 3\) 的字符包括:4, 6, 8, 2, 3,共 5 个。

正确答案:D


【真题 2】2023 年 408 第 4 题 · 加权平均码长计算

题目
在有 6 个字符组成的字符集 \(S\)$ \text{中,各个字符出现的频次分别为 3, 4, 5, 6, 8, 10,为} $\(S\) 构造的哈夫曼树的加权平均长度为( )。
A. 2.4          B. 2.5          C. 2.67          D. 2.75

【解析】

  1. 构造各步生成分支节点:
  2. 合并 3, 4 \(\to\) 生成 7,剩余序列:5, 6, 7, 8, 10
  3. 合并 5, 6 \(\to\) 生成 11,剩余序列:7, 8, 10, 11
  4. 合并 7, 8 \(\to\) 生成 15,剩余序列:10, 11, 15
  5. 合并 10, 11 \(\to\) 生成 21,剩余序列:15, 21
  6. 合并 15, 21 \(\to\) 生成 36(根节点)
  7. 应用非叶节点累加法:
  8. 所有分支节点权值相加: $\(\text{WPL} = 7 + 11 + 15 + 21 + 36 = 90\)$
  9. 计算加权平均长度:
  10. 总频次 \(\sum w_i = 3 + 4 + 5 + 6 + 8 + 10 = 36\)
  11. \[\bar{L} = \frac{90}{36} = 2.5\]

正确答案:B


【真题 3】2022 年 408 第 5 题 · 编码树性质对比

题目
对任意给定的含 \(n\) (\(n > 2\)$ \text{) 个字符的有限集} $\(S\)$ \text{,用二叉树表示} $\(S\)$ \text{的哈夫曼编码集和定长编码集,分别得到二叉树} $\(T_1\)$ \text{和} $\(T_2\)。下列叙述中,正确的是( )。
A. \(T_1\)$ \text{与} $\(T_2\) 的结点数相同
B. \(T_1\)$ \text{的高度大于} $\(T_2\) 的高度
C. 出现频次不同的字符在 \(T_1\) 中处于不同的层
D. 出现频次不同的字符在 \(T_2\) 中处于相同的层

【解析】

  • A 项错误:定长编码树 \(T_2\)$ \text{当} $\(n\)$ \text{非 2 的幂时可含度为 1 的节点,节点数不固定为} $\(2n-1\)$ \text{;哈夫曼树} $\(T_1\)$ \text{节点数恒为} $\(2n-1\)。
  • B 项错误:构造特例,设 4 个字符频次相等,哈夫曼树为满二叉树,其高度与定长编码树相同。
  • C 项错误:频次不同的字符可能处于同一层。例如频次分别为 2, 3, 4, 5:
  • 2 和 3 合并为 5;剩余序列 4, 5, 5;
  • 4 和 5 合并为 9;
  • 5 和 9 合并为 14。
  • 此时频次为 4 的字符与频次为 5 的字符深度相同。
  • D 项正确:定长编码各字符码长相等,对应二叉树中叶子节点深度均相等,位于同一层。

正确答案:D


【真题 4】2021 年 408 第 5 题 · 最小 WPL 计算

题目
若某二叉树有 5 个叶结点,其权值分别为 10、12、16、21、30,则其最小的带权路径长度(WPL)是( )。
A. 89          B. 200          C. 208          D. 289

【解析】

  1. 选取最小两权值合并(圈出非叶节点):
  2. 合并 10 + 12 = 22,剩余:16, 21, 22, 30
  3. 合并 16 + 21 = 37,剩余:22, 30, 37
  4. 合并 22 + 30 = 52,剩余:37, 52
  5. 合并 37 + 52 = 89(根节点)
  6. 非叶节点权值累加: $\(\text{WPL} = 22 + 37 + 52 + 89 = 200\)$

正确答案:B


【真题 5】2019 年 408 第 3 题 · 严格二叉树节点计算

题目
对 \(n\)$ \text{个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则} $\(n\) 的值是( )。
A. 56          B. 57          C. 58          D. 60

【解析】

  • 哈夫曼树中无度为 1 的节点(\(n_1 = 0\))。
  • \(n\) 个叶子节点对应的总节点数公式: $\(\text{Total} = 2n - 1\)$
  • 代入已知数据: $\(2n - 1 = 115 \implies 2n = 116 \implies n = 58\)$

正确答案:C


【真题 6】2018 年 408 第 5 题 · 哈夫曼编码形态判断

题目
已知字符集 \(\{a, b, c, d, e, f\}\),若各字符出现的次数分别为 6, 3, 8, 2, 10, 4,则对应字符集中各字符的哈夫曼编码可能是( )。
A. 00, 1011, 01, 1010, 11, 100
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000

【解析】

  1. 前缀特性排除:
  2. B 项中 \(a\)$ \text{为 00,} $\(d\)$ \text{为 000,} $\(a\)$ \text{是} $\(d\) 的前缀,排除 B。
  3. C 项中 \(a\)$ \text{为 10,} $\(b\)$ \text{为 1011,} $\(a\)$ \text{是} $\(b\) 的前缀,排除 C。
  4. 频次与码长反比排除:
  5. 字符 \(e\)$ \text{频次最高(10 次),码长应最短;字符} $\(d\) 频次最低(2 次),码长应最长。
  6. D 项中 \(a\)$ \text{(频次 6)编码长度为 4 位,而} $\(b\)(频次 3)编码长度仅为 2 位,不满足频次高者码长短的规则,排除 D。

正确答案:A


四、 大题应用拓展(最佳归并树思想)

【2012 年 408 第 41 题】

设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和 200 个数据元素,各表中元素按升序排列。要求通过 5 次两两合并,将 6 个表最终合并成 1 个升序表,并在最坏情况下比较的总次数达到最小。

  • 考法提炼:
  • 两表长为 \(m, n\)$ \text{,合并最坏比较次数为} $\(m + n - 1\) 次。
  • 比较总次数最少,等价于每次选取表长最短的两表合并,即哈夫曼树构造思想。
  • 得分要点:
  • 评分标准规定:说明采用哈夫曼树(最佳归并树)合并策略即可直接取得策略分。

五、 考点速记清单

  1. 节点计算:叶子 \(n\)$ \text{个} $\(\to\)$ \text{总结点} $\(2n - 1\)$ \text{个} $\(\to\)$ \text{分支节点} $\(n - 1\)$ \text{个(} $\(n_1 = 0\))。
  2. WPL 速算:草稿纸合并时,累加全部生成的新节点权值。
  3. 加权平均长度:\(\bar{L} = \text{WPL} / \sum w_i\)。
  4. 两树对比:哈夫曼编码各字符不一定同层;定长编码各字符必在同层。
  5. 解题步骤:先排前缀包含冲突 \(\to\)$ \text{再查频次与码长是否匹配} $\(\to\) 必要时画树核验。