408

数据结构

DS-04-06 哈夫曼树与哈夫曼编码

---

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	二叉树的定义与性质、树的路径长度概念、贪心思想
知识网络定位	哈夫曼树是最优二叉树，哈夫曼编码是其最重要的应用，是数据压缩的理论基础
考点热度	H级（高频重点）：近5年出现≥4次，是408数据结构的经典必考内容

---

二、知识点讲解

2.1 基本概念

路径长度：从树中一个节点到另一个节点之间的分支数目称为两节点之间的路径长度。

树的路径长度（TL）：从根节点到每个叶子节点的路径长度之和。

带权路径长度（WPL）：设二叉树有 $n$ 个叶子节点，每个叶子节点带有权值 $w_i$，从根到该叶子的路径长度为 $l_i$，则： $WPL = \sum_{i=1}^{n} w_i \times l_i$

哈夫曼树（Huffman Tree）：给定 $n$ 个带权叶子节点，构造一棵二叉树使其 WPL 最小，则该二叉树称为最优二叉树或哈夫曼树。

关键理解：

• 哈夫曼树不唯一（相同权值的不同排列方式不同），但 WPL 唯一
• 权值越大的叶子离根越近，权值越小的叶子离根越远
• 哈夫曼树中没有度为1的节点（$n_1 = 0$）

2.2 哈夫曼树的构造过程（哈夫曼算法）

算法步骤：

1. 初始化：将 $n$ 个带权叶子节点作为 $n$ 棵只有根节点的二叉树，构成森林 $F = \{T_1, T_2, \ldots, T_n\}$
2. 选取最小：从 $F$ 中选取两棵根节点权值最小的树作为新节点的左右子树（权值小的为左子树，次小的为右子树）
3. 合并：新节点的权值 = 左子树根权值 + 右子树根权值
4. 替换：将新树加入 $F$，删除原来的两棵树
5. 重复：重复步骤 2-4，直到 $F$ 中只剩一棵树

构造示例：设权值集合 $W = \{5, 29, 7, 8, 14, 23, 3, 11\}$

步骤	操作	森林中各树根的权值
初始	8棵树	{5, 29, 7, 8, 14, 23, 3, 11}
1	选3和5合并→8	{8, 29, 7, 8, 14, 23, 11}
2	选7和8(新)合并→15	{15, 29, 8, 14, 23, 11}
3	选8和11合并→19	{15, 29, 19, 14, 23}
4	选14和15合并→29	{29, 29, 19, 23}
5	选19和23合并→42	{29, 29, 42}
6	选29和29合并→58	{58, 42}
7	选42和58合并→100	{100}

最终哈夫曼树：

【图示说明】哈夫曼树：
         100
        /    \
      42      58
     /  \    /  \
   19   23  29   29
   / \       |    |
  8  11     14   ...（左右子树）
 / \
3   5 ...（继续展开）

WPL 计算：需要根据每个原始权值对应的叶子节点深度来计算。注意合并过程中产生的中间节点不是原始叶子。

2.3 哈夫曼编码

前缀编码：任何一个编码都不是其他编码的前缀，这样的编码称为前缀编码。前缀编码保证了译码的唯一性。

哈夫曼编码的构造：

1. 将每个字符的出现频率作为权值
2. 构造哈夫曼树
3. 从根到每个叶子的路径上，左分支编码为0，右分支编码为1（或相反）
4. 每个叶子节点对应的编码就是该字符的哈夫曼编码

完整构造示例：

设字符集及频率：

字符	A	B	C	D	E	F
频率	27	12	7	15	29	10

Step 1：构造哈夫曼树

步骤	合并	森林中各树根权值
初始	—	{27, 12, 7, 15, 29, 10}
1	7+10=17	{27, 12, 17, 15, 29}
2	12+15=27	{27, 17, 27, 29}
3	17+27=44	{27, 44, 29}
4	27+29=56	{44, 56}
5	44+56=100	{100}

Step 2：画出哈夫曼树（左小右大）

         100
        /    \
      44      56
     /  \    /  \
   17   27  27   29(E)
   / \      |
  7  10    15(D)
 (C) (F)  |
         12(B)
    27(A) 单独挂在56的左子树

更准确地：

           100
          /    \
        44      56
       /  \    /  \
     17   27(A) 27  29(E)
     / \        |
    7   10     15
   (C)  (F)    |
              12
             (B)

Step 3：从根到叶子编码（左0右1）：

字符	路径	编码
A(27)	10	10
B(12)	1110	1110
C(7)	000	000
D(15)	110	110
E(29)	111	111?

实际上构造需要严格按照每次选最小两棵的规则。具体编码取决于树的形态，以上为示意。关键是理解过程。

Step 4：验证前缀性——没有任何一个编码是另一个编码的前缀。

WPL = $27 \times 2 + 12 \times 4 + 7 \times 3 + 15 \times 3 + 29 \times 2 + 10 \times 3 = 54 + 48 + 21 + 45 + 58 + 30 = 256$

2.4 哈夫曼树的性质

1. $n$ 个叶子的哈夫曼树共有 $2n-1$ 个节点（因为 $n_1=0$，$n_0 = n_2+1$，所以 $n_2 = n-1$，总节点 $n_0+n_2 = 2n-1$）
2. 哈夫曼树中没有度为1的节点
3. 哈夫曼树不唯一，但 WPL 唯一

---

三、记忆与理解辅助

技巧1：哈夫曼算法口诀

"选最小两棵合为一，反复操作到剩一"

• 每次从森林中选权值最小的两棵树合并
• 新节点权值 = 两子树权值之和
• 直到森林中只剩一棵树

技巧2：哈夫曼编码的前缀性

"叶子当字符，路径当编码，天然前缀码"

• 只有叶子节点存储字符
• 从根到叶子的路径就是编码
• 因为编码终点是叶子（非其他编码的中间节点），所以天然满足前缀性

技巧3：哈夫曼树节点数公式

"$n$ 个叶子的哈夫曼树，总节点 $2n-1$，度为1的节点 $0$ 个"

推导：$n_0 = n$，$n_0 = n_2 + 1$ → $n_2 = n-1$，$n_1 = 0$ 总数 = $n_0 + n_1 + n_2 = n + 0 + (n-1) = 2n - 1$

技巧4：对比表——哈夫曼编码 vs 定长编码

对比项	定长编码	哈夫曼编码
编码长度	所有字符等长	高频字符短，低频字符长
是否前缀码	可能不是	一定是
压缩效果	无压缩	最优压缩（WPL最小）
译码难度	简单	需要查表或遍历哈夫曼树

---

四、例题与精解

例题1（基础巩固）

题目：给定权值集合 $W = \{3, 7, 8, 2, 5, 10\}$，构造哈夫曼树并计算 WPL。

命题意图：考查哈夫曼树的构造过程和 WPL 的计算。

审题分析：6个权值，需要构造含6个叶子的哈夫曼树。

解题思路：按哈夫曼算法反复选取最小两棵合并。

完整步骤：

Step 1：排序并合并

步骤	操作	森林中各树根权值
初始	—	{2, 3, 5, 7, 8, 10}
1	2+3=5	{5, 5, 7, 8, 10}
2	5+5=10	{10, 7, 8, 10}
3	7+8=15	{15, 10, 10}
4	10+10=20	{20, 15}
5	15+20=35	{35}

Step 2：哈夫曼树结构（标注原始权值的深度）：

         35
        /   \
      15     20
     /  \   /  \
    7    8 10   10
              /  \
             5    5
            / \
           2   3

Step 3：计算各叶子的深度：

• 权值7：深度2
• 权值8：深度2
• 权值2：深度4
• 权值3：深度4
• 权值5(左)：深度3
• 权值10(右)：深度2?

注意：原始权值是 {2, 3, 5, 7, 8, 10}，需要区分原始叶子和合并产生的中间节点。

原始叶子的深度：

• 2：深度4（路径 35→20→10→5→2）
• 3：深度4
• 5：深度3（路径 35→20→10→5）
• 7：深度2（路径 35→15→7）
• 8：深度2（路径 35→15→8）
• 10：深度2（路径 35→20→10）

Step 4：WPL = $2\times4 + 3\times4 + 5\times3 + 7\times2 + 8\times2 + 10\times2 = 8+12+15+14+16+20 = 85$

答案：WPL = 85。

方法反思：构造过程中合并产生的中间节点不是原始叶子，计算WPL时只算原始权值对应的叶子节点。

例题2（中等提升）

题目：字符集 {A, B, C, D, E} 出现的频率分别为 {4, 2, 6, 8, 3}，请：

1. 构造哈夫曼树
2. 给出哈夫曼编码
3. 计算编码字符串 "ABCDE" 的二进制位数（使用哈夫曼编码）

命题意图：考查哈夫曼编码的完整构造过程及应用。

完整步骤：

Step 1：构造哈夫曼树

步骤	合并	森林中各树根权值
初始	—	{2, 3, 4, 6, 8}
1	2+3=5	{5, 4, 6, 8}
2	4+5=9	{9, 6, 8}
3	6+8=14	{14, 9}
4	9+14=23	{23}

Step 2：哈夫曼树

           23
          /   \
        9      14
       / \    /  \
      5    4  6   8
     / \      (C) (D)
    2   3
   (B) (E)

等一下，步骤2中 4+5=9，但 4 < 5 < 6，所以选 4 和 5 合并是正确的（因为 4 和 5 是当前最小的两个）。

验证：步骤1后 {5, 4, 6, 8}，最小两个是 4 和 5。正确。

Step 3：哈夫曼编码（左0右1）

字符	频率	深度	编码
B	2	3	000
E	3	3	001
A	4	2	01
C	6	2	10
D	8	2	11

Step 4：WPL = $2\times3 + 3\times3 + 4\times2 + 6\times2 + 8\times2 = 6+9+8+12+16 = 51$

"ABCDE" 的编码：000 + 001 + 01 + 10 + 11 = 000001011011，共12位。

若用定长编码（3位/字符），"ABCDE" 需要 $5 \times 3 = 15$ 位。哈夫曼编码节省了3位。

答案：哈夫曼编码如上表，"ABCDE" 编码后共12位。

---

五、考情分析

项目	内容
考查频次	近5年约4次，几乎每年都有
常见题型	选择题（判断哈夫曼编码正确性、求WPL）、大题（完整构造哈夫曼树和编码）
分值占比	选择题2分 + 大题5-8分
命题趋势	哈夫曼编码的构造过程是必考内容；近年倾向于综合考查（如给定编码字符串求原始字符、判断是否为哈夫曼编码）
典型考点	①哈夫曼树构造 ②WPL计算 ③前缀编码的判断 ④哈夫曼编码的编码/译码

---

六、易错点提醒

易错点1

• 错误表现：构造哈夫曼树时，合并产生的中间节点也被当作原始叶子参与WPL计算
• 错误原因：混淆了原始叶子和中间节点
• 正确理解：WPL 只对原始叶子节点计算。中间节点（合并产生的新节点）不参与WPL计算

易错点2

• 错误表现：选最小两棵树时，没有严格按照权值排序后选最小
• 错误原因：贪心策略执行不严格
• 正确理解：每次必须选当前森林中权值最小的两棵。如果有多个相同权值，选任意两个均可（不影响WPL）

易错点3

• 错误表现：认为哈夫曼树唯一
• 错误原因：忽略了相同权值的不同排列方式
• 正确理解：当存在多个相同最小权值时，选择不同组合会导致不同的树形，但WPL相同

易错点4

• 错误表现：给哈夫曼编码时，左右分支的0/1分配不一致
• 错误原因：没有统一规则
• 正确理解：可以在开始时统一规定"左0右1"或"左1右0"，但整棵树必须一致。不同规定导致不同编码，但都是合法的哈夫曼编码

易错点5

• 错误表现：计算 $n$ 个叶子的哈夫曼树总节点数时写成 $n-1$ 或 $2n$
• 错误原因：没有掌握 $n_0 = n_2 + 1$ 和 $n_1 = 0$ 的性质
• 正确理解：$n_0 = n$，$n_1 = 0$，$n_2 = n-1$，总节点 $= 2n-1$

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义
• 哈夫曼编码构造过程依据 David A. Huffman 1952年原始论文的算法描述