🌳 哈夫曼树与哈夫曼编码 · 考点全解析
笔记说明
本笔记涵盖哈夫曼树构造、WPL 计算、哈夫曼编码、K 叉哈夫曼树、判定性质等全部考点类型,每类配公式、符号说明、历年真题例题与详解。 每道例题都附有「题眼」——告诉你在考场上拿到这道题该从哪里下手。 适用:408 考研 / 软考 / 数据结构期末。
📌 一、核心概念
定义
哈夫曼树(Huffman Tree):又称最优二叉树,是一类带权路径长度(WPL)最短的二叉树。 哈夫曼编码(Huffman Coding):基于哈夫曼树构造的前缀编码,用于数据压缩,使平均码长最短。
🔑 关键术语
| 术语 | 含义 |
|---|---|
| 路径长度 | 从根到该结点经过的边数 |
| 结点的带权路径长度 | w_i × l_i |
| 树的带权路径长度 | WPL = Σ(w_i × l_i) |
| 前缀编码 | 任一编码都不是另一编码的前缀 |
| 加权平均长度 | WPL / Σw_i,即平均码长 |
🧮 核心公式
快捷计算
WPL = 所有非叶结点的权值之和(每次组合的新节点),无需逐叶计算深度! 注:别遗漏了最后组成的那个节点
🔤 符号说明(重要)
这些符号你必须先搞懂
w_i:第 i 个叶子结点的权值。在哈夫曼树题目中,权值通常就是题目给出的「频次」,有时也可能是字符本身代表的数字、概率等。l_i:第 i 个叶子结点到根结点的路径长度(经过的边数,根为第 0 层)。n:叶子结点总数,也就是参与构造的字符(或元素)个数。K:K 叉树的分支数。二叉树 K=2,三叉树 K=3。Σw_i:所有权值之和,也就是所有频次加起来的总频次。WPL:带权路径长度,是一个总和,不是平均值。L_avg:加权平均长度,等于WPL / Σw_i,也就是平均每个字符的编码长度。
最容易搞混的一点
题目给的「频次」就是权值
w_i,不是字符本身! 字符只是名字,频次才是构造哈夫曼树时真正参与计算的数据。 例如:「字符 A 频次为 3」→ 权值就是 3,不是 A。
🧩 二、考点分类详解
🟢 类型一:构造哈夫曼树并求 WPL
构造规则(贪心)
- 所有叶子作为独立结点
- 每次取两个权值最小的结点合并,新结点权值 = 两者之和
- 重复直到只剩一个结点
例题:给定权值集合 {3, 5, 6, 9, 12},构造哈夫曼树并求 WPL。
题眼
看到「构造哈夫曼树」+「求 WPL」,立刻反应: ① 用贪心,每次挑两个最小的; ② WPL 不用逐个叶子算,直接把所有合并出来的非叶结点加起来就行。
解答:
| 步骤 | 合并 | 新结点 | 剩余集合 |
|---|---|---|---|
| 1 | 3 + 5 | 8 | {6, 8, 9, 12} |
| 2 | 6 + 8 | 14 | {9, 12, 14} |
| 3 | 9 + 12 | 21 | {14, 21} |
| 4 | 14 + 21 | 35 | {35} |
🟢 类型二:结点总数 ↔ 叶子结点数
公式:结点总数 = 2n - 1
例题(软考真题):一棵哈夫曼树共有 9 个结点,叶子结点个数为?
题眼
看到「哈夫曼树」+「结点总数」+「求叶子数」,直接套公式
2n - 1 = 总结点数(n是叶子节点)。不存在度为1的节点,他从叶子节点反推上去。 🔴二叉树恒满足:n2=n0-1(度为2的节点等于度为0的叶子节点减一)。再加上n=n0+n1+n2(n1是0) 将关系带入有n=2n0-1 记住:二叉哈夫曼树没有度为 1 的结点(),且 ,所以总结点数永远是2n - 1。
解答:2n - 1 = 9 → 2n = 10 → n = 5
陷阱
千万别把公式记成
n - 1或2n + 1,移项时注意是+ 1再除以 2!
🟢 类型三:判定前缀编码
前缀编码判定
任一编码都不是另一编码的前缀,即不存在一个编码是另一个的开头。
例题(2014 年 408 真题):以下编码方案中,不是前缀编码的是?
- A.
01, 0000, 0001, 001, 1 - B.
011, 000, 001, 010, 1 - C.
000, 001, 010, 011, 100 - D.
0, 100, 110, 1110, 1100
题眼
看到「前缀编码」,立刻做一件事:逐个检查有没有一个编码是另一个的前缀。 技巧:把编码按长度排序,短的去和长的比开头。
解答:
- A:
01不是0000/0001/001的前缀,1不是其他任何编码的前缀 ✅ - B:
1不是其他编码的前缀,011不是000/001/010的前缀 ✅ - C:所有编码长度相同,互相不构成前缀 ✅
- D:
110是1100的前缀 ❌(同时存在110和1100,说明110不可能是叶子节点,否则1100无法编码)
答案:D
🟢 类型四:K 叉哈夫曼树(重点难点)
核心陷阱
构造 K 叉哈夫曼树时,若
(n-1) mod (K-1) ≠ 0,需补充权值为 0 的虚结点,否则第一次合并不足 K 个结点,构造出的不是最优树!
补虚结点数公式:
验证:
- n=6, K=3:
r = 5 mod 2 = 1,补2-1 = 1个 ✅ - n=5, K=3:
r = 4 mod 2 = 0,补 0 个 ✅
例题(2013 年 408 真题):三叉树 T 中 6 个叶结点权值为 2, 3, 4, 5, 6, 7,WPL 最小是多少?
题眼
看到「K 叉」+「WPL 最小」,第一件事:先算
(n-1) mod (K-1)。 如果结果不为 0,必须先补 0,否则后面全错! 补完 0 之后再按「每次取 K 个最小」合并。
解答:
n = 6, K = 3,r = (6-1) mod (3-1) = 1 ≠ 0- 补虚结点:
(3-1) - 1 = 1个 → 加入权值0 - 集合变为
{0, 2, 3, 4, 5, 6, 7}
| 轮次 | 取最小三个 | 合并 | 剩余 |
|---|---|---|---|
| 1 | 0, 2, 3 | 5 | {4, 5, 5, 6, 7} |
| 2 | 4, 5, 5 | 14 | {6, 7, 14} |
| 3 | 6, 7, 14 | 27 | {27} |
WPL 快捷算法(推荐,不用数深度):
验证(逐叶计算):
🟢 类型五:判定结点序列是否属于同一棵哈夫曼树
判定依据(铁律)
- 同根性:两条路径的根结点权值必须相同。
- 严格递减(正权值下):从根到叶,路径上的权值必须严格递减(父 > 子)。
- 分叉守恒:若两条路径在某祖先结点 处分叉(走向不同子树),则这两条路径在 之后的第一个结点权值之和 必须 的权值(如果这两个结点恰好是 的直接左、右孩子,则权值之和 严格等于 )。
例题(2015 年 408 真题,已统一转换为从根到叶的顺序):下列给出的从根分别到两个叶结点的路径上的权值序列,能属于同一棵哈夫曼树的是?
- A.
24, 10, 5和24, 10, 7 - B.
24, 12, 5和24, 12, 7(注:真题原选项为5, 12, 24和7, 12, 24) - C.
24, 10, 10和24, 14, 11 - D.
24, 10, 5和24, 14, 6
题眼
看到「路径序列」+「同一棵哈夫曼树」,先看单条路径是否满足
父 > 子,再看分叉点是否满足左子 + 右子 = 父!
解答:
- A 错:两条路径都经过同一个结点
10,随后分叉走向叶子5和7。但5 + 7 = 12 > 10,子孙权值之和超过了祖先10,绝对不可能 ❌。 - B 错:两条路径在根
24下都经过12。- 情况 1:若两个
12是同一个结点,则24的另一个孩子也是24 - 12 = 12(是个叶子),而12往下分叉成叶子5和7。此时四个叶子权值为{5, 7, 12}。但按哈夫曼树规则,{5, 7, 12}合并完就结束了,没有第 4 个叶子,矛盾;若12不是叶子,题目又没交代。 - 情况 2:若两个
12是24的左、右两个不同孩子,那么左孩子12有个叶子5(另一半是7),右孩子12有个叶子7(另一半是5),此时叶子集合为{5, 5, 7, 7}!注意:如果叶子是{5, 5, 7, 7},哈夫曼树第一步必须先合并最小的两个:5 + 5 = 10,绝不可能合并出两个12!❌(这是 2015 真题最精妙的坑!)
- 情况 1:若两个
- C 错:第一条路径
24, 10, 10中出现了两个10(除非有 0 权值结点,否则哈夫曼树父必大于子) ❌。 - D 对:在根
24处分叉为左孩子10和右孩子14(10 + 14 = 24);10拆分为叶子5和另一个结点5;14拆分为叶子6和另一个结点8。此时叶子为{5, 5, 6, 8},合并过程:5+5=10,6+8=14,10+14=24,完美契合哈夫曼规则 ✅!
答案:D
🟢 类型六:计算加权平均编码长度
公式说明
加权平均长度 = WPL ÷ Σw_i 其中
Σw_i是所有频次(权值)之和。 这个公式的含义是:平均每个字符用多少位编码。
例题(2018 年 408 真题):字符集 S 中 6 个字符频次分别为 3, 4, 5, 6, 8, 10,加权平均长度为?
题眼
看到「加权平均长度」,脑子里立刻分两步: 第一步:算 WPL(合并出的非叶结点全加起来); 第二步:除以总频次(题目给的所有频次相加)。 ⚠️ 千万别只算到 WPL 就选答案,那是最常见的失分点!
解答:
| 步骤 | 合并 | 新结点 |
|---|---|---|
| 1 | 3 + 4 | 7 |
| 2 | 5 + 6 | 11 |
| 3 | 7 + 8 | 15 |
| 4 | 10 + 11 | 21 |
| 5 | 15 + 21 | 36 |
🟢 类型七:判定哈夫曼树性质
例题(2010 年 408 真题相关经典题):关于哈夫曼树的叙述,错误的是?
- A. 该树一定是一棵完全二叉树
- B. 树中一定没有度为 1 的结点
- C. 树中存在两个权值最小的结点一定是兄弟结点
- D. 任一非叶结点的权值一定不小于其子树中任一结点的权值
解答:
- A 错:哈夫曼树不一定是完全二叉树(例如
{1, 2, 4, 8}构造出来是一条偏斜的树)。 - B ✅:严格二叉树,无度为 1 的结点。
- C ✅:最先合并的两个最小结点必为兄弟。
- D ✅:父 = 子之和(正权值下),必大于子孙。
答案:A
考场严谨性避坑(针对选项 C 和 D 的原版表述)
- 如果选项 C 写成“树中任意两个权值最小的结点一定是兄弟”:当最小权值有多个重复时(如
{1, 1, 1, 2}),前两个1合并成2,第三个1会和2合并,此时第三个1和前两个1不是兄弟!所以严谨说法是“存在两个最小权值结点是兄弟”(或在各权值互不相等时一定成立)。- 如果选项 D 写成“任一非叶结点的权值一定不小于下一层任一结点的权值”:在绝大多数教材单选题中默认其正确,但在极端构造下可能存在反例,而“不小于其子树中任一结点”则 100% 绝对正确。单选题遇到 A 这种明显错误时直接选 A 即可!
🟢 类型八:编码长度上限 → 最多编码字符数
例题(王道):哈夫曼编码长度不超过 4,已对两个字符编码为 1 和 01,最多还可对几个字符编码?
题眼
看到「编码长度不超过 X」+「已占用若干编码」,把它想成一棵深度为 X 的满二叉树。 已占用的编码会堵死某些分支,剩下的空位就是还能编码的字符数。
解答:
- 深度 4 的满二叉树,叶子在第 4 层,共
2^4 = 16个叶子位。 - 编码
1占用第 1 层的一个分支,堵死以1开头的全部2^(4-1) = 8个叶子位。 - 编码
01占用第 2 层的一个分支,堵死以01开头的全部2^(4-2) = 4个叶子位。 - 剩余可用叶子位 =
16 - 8 - 4 = 4。
答案:4
🟢 类型九:构造哈夫曼编码并压缩数据
例题:字符 A, B, C, D, E 频次 {5, 9, 12, 13, 16},构造哈夫曼编码,并求压缩率。
解答:
| 步骤 | 合并 | 新结点 |
|---|---|---|
| 1 | 5 + 9 | 14 |
| 2 | 12 + 13 | 25 |
| 3 | 14 + 16 | 30 |
| 4 | 25 + 30 | 55 |
编码方案(左 0 右 1):
- A:
000, B:001, C:10, D:11, E:01(注:14 和 16 合并为 30,25 和 30 合并为 55,若 30 在左、25 在右,则 A(5):000, B(9):001, E(16):01, C(12):10, D(13):11)
WPL = 55 + 30 + 25 + 14 = 124
压缩对比
定长编码需
⌈log₂5⌉ = 3位,哈夫曼编码平均2.25位,节省了(3 - 2.25) / 3 = 25%的空间。
🟢 类型十:判断题 / 综合概念题
| 命题 | 正误 |
|---|---|
| 哈夫曼树是唯一的 | ❌ |
| 哈夫曼树 WPL 是唯一的 | ✅ |
| 哈夫曼树一定是完全二叉树 | ❌ |
| 二叉哈夫曼树没有度为 1 的结点 | ✅ |
| 哈夫曼编码是前缀编码 | ✅ |
| 频率高的字符编码长度一定不长于频率低的字符 | ✅ |
| 权值相同合并顺序不同,WPL 会变 | ❌ |