哈夫曼树（最优二叉树）- 期末核心考点整理
一、 哈夫曼树的定义
给定n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。
关键术语解释
- 路径长度：从树中一个结点到另一个结点之间的分支数目。
- 树的路径长度：从根结点到所有叶子结点的路径长度之和。
- 带权路径长度(WPL)：叶子结点的权值乘以其到根结点的路径长度，所有叶子结点的带权路径长度之和。
- 公式：WPL=∑i=1nwi×liWPL=\sum_{i=1}^n w_i \times l_iWPL=∑i=1nwi×li
- wiw_iwi：第iii个叶子结点的权值；lil_ili：第iii个叶子结点到根的路径长度
- 叶子结点：哈夫曼树中，只有叶子结点带有权值，非叶子结点的权值为其左右子树权值之和。
二、 哈夫曼树的核心特点
- 结构特点
- 哈夫曼树中没有度为 1 的结点，只有度为 0（叶子）和度为 2（非叶子）的结点，也叫严格二叉树/正则二叉树。
- 若叶子结点数为nnn，则非叶子结点数为n−1n-1n−1，总结点数为2n−12n-12n−1。
- 权值分布特点
- 权值越大的叶子结点，离根结点越近；权值越小的叶子结点，离根结点越远。
- 哈夫曼树的形态不唯一，但最小带权路径长度(WPL)是唯一的。
- 构建特点
- 构建过程采用贪心算法，每次选择当前权值最小的两个结点合并成一个新的父结点。
三、 哈夫曼树的构建步骤（期末高频考点）
- 初始化：将nnn个权值对应的结点分别作为nnn棵只含单个结点的二叉树，构成一个森林FFF。
- 合并操作
- 从森林FFF中选取两棵根结点权值最小的二叉树，作为左、右子树合并成一棵新二叉树。
- 新二叉树的根结点权值 = 左子树根权值 + 右子树根权值。
- 更新森林：将合并后的新二叉树加入森林FFF，同时移除原来的两棵子树。
- 重复步骤：重复 2、3 步，直到森林FFF中只剩下一棵二叉树，该树即为哈夫曼树。
例题演示
已知权值 {5, 6, 7, 8, 15}，构建哈夫曼树并计算 WPL
- 第一次合并：5+6=11 → 森林变为 {7, 8, 11, 15}
- 第二次合并：7+8=15 → 森林变为 {11, 15, 15}
- 第三次合并：11+15=26 → 森林变为 {15, 26}
- 第四次合并：15+26=41 → 哈夫曼树构建完成
- 计算 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 计算只针对叶子结点，非叶子结点不计入。
- 哈夫曼树的根结点权值 = 所有叶子结点权值之和。
五、 高频选择题/填空题速记
- 含nnn个叶子结点的哈夫曼树，总结点数 =2n−1\boldsymbol{2n-1}2n−1。
- 哈夫曼树的带权路径长度 WPL 是所有可能二叉树中最小的。
- 哈夫曼编码是一种最优前缀编码，广泛应用于数据压缩（如 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。
