🌳 哈夫曼树与哈夫曼编码 · 考点全解析

笔记说明

本笔记涵盖哈夫曼树构造、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

构造规则(贪心)

  1. 所有叶子作为独立结点
  2. 每次取两个权值最小的结点合并,新结点权值 = 两者之和
  3. 重复直到只剩一个结点

例题:给定权值集合 {3, 5, 6, 9, 12},构造哈夫曼树并求 WPL。

题眼

看到「构造哈夫曼树」+「求 WPL」,立刻反应: ① 用贪心,每次挑两个最小的; ② WPL 不用逐个叶子算,直接把所有合并出来的非叶结点加起来就行。

解答:

步骤合并新结点剩余集合
13 + 58{6, 8, 9, 12}
26 + 814{9, 12, 14}
39 + 1221{14, 21}
414 + 2135{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}
轮次取最小三个合并剩余
10, 2, 35{4, 5, 5, 6, 7}
24, 5, 514{6, 7, 14}
36, 7, 1427{27}

WPL 快捷算法(推荐,不用数深度):

验证(逐叶计算):


🟢 类型五:判定结点序列是否属于同一棵哈夫曼树

判定依据(铁律)

  1. 同根性:两条路径的根结点权值必须相同。
  2. 严格递减(正权值下):从根到叶,路径上的权值必须严格递减(父 > 子)。
  3. 分叉守恒:若两条路径在某祖先结点 处分叉(走向不同子树),则这两条路径在 之后的第一个结点权值之和 必须 的权值(如果这两个结点恰好是 的直接左、右孩子,则权值之和 严格等于 )。

例题(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 真题最精妙的坑!)
  • 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 就选答案,那是最常见的失分点!

解答:

步骤合并新结点
13 + 47
25 + 611
37 + 815
410 + 1121
515 + 2136

🟢 类型七:判定哈夫曼树性质

例题(2010 年 408 真题相关经典题):关于哈夫曼树的叙述,错误的是?

  • A. 该树一定是一棵完全二叉树
  • B. 树中一定没有度为 1 的结点
  • C. 树中存在两个权值最小的结点一定是兄弟结点
  • D. 任一非叶结点的权值一定不小于其子树中任一结点的权值

解答:

  • A 错:哈夫曼树不一定是完全二叉树(例如 {1, 2, 4, 8} 构造出来是一条偏斜的树)。
  • B ✅:严格二叉树,无度为 1 的结点。
  • C ✅:最先合并的两个最小结点必为兄弟。
  • D ✅:父 = 子之和(正权值下),必大于子孙。

答案:A

考场严谨性避坑(针对选项 C 和 D 的原版表述)

  1. 如果选项 C 写成“树中任意两个权值最小的结点一定是兄弟”:当最小权值有多个重复时(如 {1, 1, 1, 2}),前两个 1 合并成 2,第三个 1 会和 2 合并,此时第三个 1 和前两个 1 不是兄弟!所以严谨说法是“存在两个最小权值结点是兄弟”(或在各权值互不相等时一定成立)。
  2. 如果选项 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},构造哈夫曼编码,并求压缩率。

解答:

步骤合并新结点
15 + 914
212 + 1325
314 + 1630
425 + 3055

编码方案(左 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 会变❌