9.数据结构哈夫曼树期末考试速览

哈夫曼树（最优二叉树）- 期末核心考点整理

一、 哈夫曼树的定义

给定n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。

关键术语解释

1. 路径长度：从树中一个结点到另一个结点之间的分支数目。
   • 树的路径长度：从根结点到所有叶子结点的路径长度之和。
2. 带权路径长度(WPL)：叶子结点的权值乘以其到根结点的路径长度，所有叶子结点的带权路径长度之和。
   • 公式：WPL=∑i=1nwi×liWPL=\sum_{i=1}^n w_i \times l_iWPL=∑i=1n​wi​×li​
   • wiw_iwi​：第iii个叶子结点的权值；lil_ili​：第iii个叶子结点到根的路径长度
3. 叶子结点：哈夫曼树中，只有叶子结点带有权值，非叶子结点的权值为其左右子树权值之和。

二、 哈夫曼树的核心特点

1. 结构特点
   • 哈夫曼树中没有度为 1 的结点，只有度为 0（叶子）和度为 2（非叶子）的结点，也叫严格二叉树/正则二叉树。
   • 若叶子结点数为nnn，则非叶子结点数为n−1n-1n−1，总结点数为2n−12n-12n−1。
2. 权值分布特点
   • 权值越大的叶子结点，离根结点越近；权值越小的叶子结点，离根结点越远。
   • 哈夫曼树的形态不唯一，但最小带权路径长度(WPL)是唯一的。
3. 构建特点
   • 构建过程采用贪心算法，每次选择当前权值最小的两个结点合并成一个新的父结点。

三、 哈夫曼树的构建步骤（期末高频考点）

1. 初始化：将nnn个权值对应的结点分别作为nnn棵只含单个结点的二叉树，构成一个森林FFF。
2. 合并操作
   • 从森林FFF中选取两棵根结点权值最小的二叉树，作为左、右子树合并成一棵新二叉树。
   • 新二叉树的根结点权值 = 左子树根权值 + 右子树根权值。
3. 更新森林：将合并后的新二叉树加入森林FFF，同时移除原来的两棵子树。
4. 重复步骤：重复 2、3 步，直到森林FFF中只剩下一棵二叉树，该树即为哈夫曼树。

例题演示

已知权值 {5, 6, 7, 8, 15}，构建哈夫曼树并计算 WPL

1. 第一次合并：5+6=11 → 森林变为 {7, 8, 11, 15}
2. 第二次合并：7+8=15 → 森林变为 {11, 15, 15}
3. 第三次合并：11+15=26 → 森林变为 {15, 26}
4. 第四次合并：15+26=41 → 哈夫曼树构建完成
5. 计算 WPL：5×3+6×3+7×2+8×2+15×1=15+18+14+16+15=785\times3 + 6\times3 + 7\times2 + 8\times2 + 15\times1 = 15+18+14+16+15=785×3+6×3+7×2+8×2+15×1=15+18+14+16+15=78

四、 期末易考知识点与题型总结

1. 概念判断题

• 考点 1：哈夫曼树没有度为 1 的结点 →正确
• 考点 2：权值越大的叶子离根越近 →正确
• 考点 3：哈夫曼树的 WPL 一定最小 →正确
• 考点 4：给定权值的哈夫曼树形态唯一 →错误

2. 计算题

• 考点 1：根据权值构建哈夫曼树，并计算 WPL（必考）
• 考点 2：已知叶子结点数nnn，求总结点数 →2n−12n-12n−1
• 考点 3：已知 WPL 和部分权值，反推缺失的权值

3. 哈夫曼编码（延伸考点，常结合哈夫曼树考）

• 原理：左分支编码为 0，右分支编码为 1，从根到叶子的路径编码即为该叶子的哈夫曼编码。
• 特点：哈夫曼编码是前缀编码（任意一个编码都不是另一个编码的前缀），可保证解码无歧义。
• 题型：根据哈夫曼树生成编码，或根据编码反推树的结构。

4. 易错点提醒

• 合并时必须选当前最小的两个权值，顺序错误会导致 WPL 计算错误。
• WPL 计算只针对叶子结点，非叶子结点不计入。
• 哈夫曼树的根结点权值 = 所有叶子结点权值之和。

五、 高频选择题/填空题速记

1. 含nnn个叶子结点的哈夫曼树，总结点数 =2n−1\boldsymbol{2n-1}2n−1。
2. 哈夫曼树的带权路径长度 WPL 是所有可能二叉树中最小的。
3. 哈夫曼编码是一种最优前缀编码，广泛应用于数据压缩（如 ZIP 压缩）。

---

哈夫曼树核心考点选择题（4题）

考点一：哈夫曼树结点数量关系（含n个叶子结点的总结点数=2n-1）

第1题：已知一棵哈夫曼树包含8个叶子结点，该树的总结点数为（ ）

• A. 14

• B. 15

• C. 16

• D. 17

答案：B 解析：根据公式“含n个叶子结点的哈夫曼树总结点数=2n-1”，代入n=8可得2×8-1=15，故选B。

第2题：某哈夫曼树的总结点数为23，该树中叶子结点的个数是（ ）

• A. 11

• B. 12

• C. 22

• D. 23

答案：B 解析：设叶子结点数为n，由总结点数=2n-1可得2n-1=23，解得n=12，故选B。

考点二：哈夫曼编码的特性与编码原理

第3题：关于哈夫曼编码的描述，下列说法正确的是（ ）

• A. 哈夫曼编码不是前缀编码，解码时易产生歧义

• B. 哈夫曼编码是最优前缀编码，可用于数据压缩

• C. 哈夫曼编码的编码长度固定，便于快速存储

• D. 哈夫曼编码仅适用于文本数据，无法处理图像数据

答案：B 解析：哈夫曼编码的核心特性是“最优前缀编码”，任意编码都不是其他编码的前缀，保证解码无歧义，且因编码长度与权值匹配，压缩效率高，广泛应用于ZIP等压缩场景，故选B。A、C、D均不符合哈夫曼编码的特性。

第4题：在哈夫曼编码的生成规则中，若从根结点到某叶子结点的路径为“根→左子树→右子树→左子树”，则该叶子结点的哈夫曼编码为（ ）

• A. 010

• B. 011

• C. 100

• D. 101

答案：A 解析：哈夫曼编码规则为“左分支编码为0，右分支编码为1”，该路径依次经过左（0）、右（1）、左（0），拼接后编码为010，故选A。