Appearance
第3章 哈夫曼树与特殊树
🎯 本章学习目标
通过本章的学习，你将能够：
- 掌握哈夫曼树：理解哈夫曼树的构造过程，会计算带权路径长度 WPL
- 理解哈夫曼编码：掌握前缀编码特性，能根据哈夫曼树生成编码
- 掌握完全二叉树：理解完全二叉树的性质，会用数组存储
- 掌握二叉排序树：理解BST的定义，掌握插入和查找操作
- 了解格雷编码：知道格雷码的特点和生成方法
- 计算WPL：能用多种方法计算哈夫曼树的带权路径长度
- 分析BST中序遍历：知道BST中序遍历结果是升序的
- 处理删除操作：理解BST删除节点的三种情况
- 区分各类树：清楚哈夫曼树、完全二叉树、BST各自的特点
- 应对真题题型：能解决选择、判断、计算等各类特殊树的题目
🗺️ 本章知识图谱
哈夫曼树与特殊树
├── 哈夫曼树
│ ├── 定义：带权路径长度最小的二叉树
│ ├── 构造方法：每次选最小的两个合并
│ ├── WPL（带权路径长度）
│ │ ├── = Σ(权值 × 深度)
│ │ └── = 所有非叶子节点权值之和
│ ├── 特点：没有度为1的节点
│ └── 哈夫曼编码
│ ├── 前缀编码（无歧义）
│ ├── 左0右1
│ └── 频率高的字符编码短
├── 完全二叉树
│ ├── 定义：前k-1层满，最后一层左连续
│ ├── 性质
│ │ ├── 深度 = floor(log2 n) + 1
│ │ ├── 节点i的左孩子 = 2i
│ │ ├── 节点i的右孩子 = 2i+1
│ │ └── 节点i的父节点 = i/2
│ ├── 数组存储（从下标1开始）
│ └── 满二叉树是特殊的完全二叉树
├── 二叉排序树（BST）
│ ├── 定义：左小右大
│ ├── 中序遍历 = 升序序列
│ ├── 查找：从根开始比较
│ ├── 插入：找到空位插入
│ └── 删除
│ ├── 叶子节点：直接删
│ ├── 一个孩子：孩子接替
│ └── 两个孩子：右子树最小值（或左子树最大值）接替
└── 格雷编码
├── 特点：相邻两个数只有一位不同
├── 生成公式：G(n) = n XOR (n>>1)
└── 应用：出错率低、 Karnaugh图本书第3章 · 哈夫曼树与特殊树
主题：哈夫曼树、完全二叉树、二叉排序树、哈夫曼编码、格雷编码
考纲要求：(2) 掌握哈夫曼树、完全二叉树、二叉排序树的相关概念和应用；(3) 理解哈夫曼编码、格雷编码相关原理并能进行简单应用。
一、哈夫曼树（Huffman Tree）
1.1 什么是哈夫曼树？
哈夫曼树又叫最优二叉树，是一类带权路径长度（WPL）最短的二叉树。
核心概念：
| 术语 | 含义 |
|---|---|
| 路径长度 | 从根到该节点经过的边数 |
| 带权路径长度 | 节点的权值 × 该节点的路径长度 |
| 树的 WPL | 所有叶子节点的带权路径长度之和 |
哈夫曼树的核心目标：让权值大的叶子节点尽量靠近根，从而使 WPL 最小。
1.2 构造方法（贪心策略）
算法步骤：
- 将 n 个权值作为 n 棵只有根节点的树，放入优先队列（小根堆）
- 每次从堆中取出权值最小的两棵树，合并为一棵新树
- 新树的根节点权值 = 两棵子树根节点权值之和
- 将新树放回堆中
- 重复 2~4，直到堆中只剩一棵树
⚠️ 高频易错：哈夫曼树中没有度为 1 的节点（即每个内部节点都有恰好 2 个孩子）。n 个叶子节点的哈夫曼树共有 2n-1 个节点。
1.3 WPL 计算
方法一：逐个计算每个叶子节点的 权值 × 路径长度，再求和。
方法二（更快）：所有内部节点的权值之和 = WPL。
这是因为每个内部节点的权值都会在其子孙叶子节点的路径中被"计入"，等价于累加。
1.4 C++ 代码模板
cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 使用小根堆构造哈夫曼树，返回 WPL
int huffmanWPL(vector<int>& weights) {
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
for (int w : weights) pq.push(w);
int wpl = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop(); // 最小
int b = pq.top(); pq.pop(); // 次小
int sum = a + b;
wpl += sum; // 累加内部节点权值
pq.push(sum);
}
return wpl;
}
int main() {
vector<int> weights = {2, 3, 6, 7, 1, 4, 8};
cout << "WPL = " << huffmanWPL(weights) << endl;
return 0;
}1.5 考试常见考法
- ✅ 给定权值集合，要求画出哈夫曼树并计算 WPL
- ✅ 选择题：哈夫曼树中不存在度为 1 的节点
- ✅ 选择题：n 个叶子的哈夫曼树有 2n-1 个节点
- ✅ 给出一组权值，判断哪些节点的编码最短（权值越大编码越短）
二、完全二叉树（Complete Binary Tree）
2.1 定义
一棵深度为 h 的二叉树，除第 h 层外，其它各层节点数都达到最大，且第 h 层的节点从左到右依次排列，这样的二叉树称为完全二叉树。
关键词：从左到右连续，不能有空位。
2.2 核心性质（节点编号与父子关系）
对节点从 1 开始编号（按层序），则对编号为 i 的节点：
| 关系 | 公式 |
|---|---|
| 父节点 | i / 2（i=1 时为根，无父节点） |
| 左孩子 | 2 * i（若 2i > n 则无左孩子） |
| 右孩子 | 2 * i + 1（若 2i+1 > n 则无右孩子） |
⚠️ 高频易错：编号必须从 1 开始！如果从 0 开始，则父节点为
(i-1)/2，左孩子为2i+1，右孩子为2i+2。
2.3 数组存储
完全二叉树可以用数组紧凑存储（无需指针），这也是堆（Heap） 的底层结构。
cpp
// 数组存储的完全二叉树（小根堆示例）
int heap[100005];
int heapSize = 0;
void pushUp(int i) {
while (i > 1 && heap[i] < heap[i / 2]) {
swap(heap[i], heap[i / 2]);
i /= 2;
}
}
void push(int val) {
heap[++heapSize] = val;
pushUp(heapSize);
}
int pop() {
int res = heap[1];
heap[1] = heap[heapSize--];
// 下沉调整
int i = 1;
while (2 * i <= heapSize) {
int child = 2 * i;
if (child + 1 <= heapSize && heap[child + 1] < heap[child])
child++;
if (heap[i] <= heap[child]) break;
swap(heap[i], heap[child]);
i = child;
}
return res;
}2.4 三种二叉树的辨析（必考辨析！）
| 名称 | 定义 | 关键特征 |
|---|---|---|
| 满二叉树 | 深度为 h，共有 2^h - 1 个节点 | 每一层都"满"，每个内部节点都有 2 个孩子 |
| 完满二叉树 | 每个节点要么是叶子，要么恰好有 2 个孩子 | 不存在度为 1 的节点（哈夫曼树就是完满二叉树） |
| 完全二叉树 | 从上到下、从左到右连续填充 | 最后一层可以不满，但必须靠左排列 |
关系：满二叉树（完美二叉树）一定是完全二叉树；但完满二叉树（无一度节点）不一定是完全二叉树——完满只要求每个节点 0 或 2 个孩子，不要求《连续靠左》填充。完全二叉树也不一定满或完满。简单说：满 ⊊ 完全，而完满与完全互不包含。
简单记忆：满 = 全满；完满 = 没一度节点；完全 = 连续靠左。
三、二叉排序树（BST）
3.1 定义
二叉排序树（Binary Search Tree, BST），又称二叉查找树，满足：
- 左子树中所有节点的值 < 根节点的值
- 右子树中所有节点的值 > 根节点的值
- 左右子树也分别是二叉排序树
核心性质：中序遍历 BST 得到的是递增有序序列。
3.2 查找操作
从根节点开始，比当前大走右子树，比当前小走左子树，相等则找到。
cpp
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
// 查找
TreeNode* search(TreeNode* root, int target) {
if (root == nullptr) return nullptr;
if (target == root->val) return root;
if (target < root->val) return search(root->left, target);
return search(root->right, target);
}3.3 插入操作
类似查找，找到空位就插入。
cpp
TreeNode* insert(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val < root->val) root->left = insert(root->left, val);
else if (val > root->val) root->right = insert(root->right, val);
return root;
}3.4 删除操作（三种情况，考试重点！）
| 情况 | 处理方式 |
|---|---|
| 叶子节点 | 直接删除 |
| 只有一个孩子 | 用孩子替代该节点 |
| 有两个孩子 | 找到右子树中的最小节点（中序后继），用其值替换当前节点，然后删除那个最小节点 |
cpp
// 找右子树最小节点
TreeNode* findMin(TreeNode* root) {
while (root->left) root = root->left;
return root;
}
// 删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 情况1：叶子节点
if (!root->left && !root->right) {
delete root;
return nullptr;
}
// 情况2：只有一个孩子
if (!root->left) {
TreeNode* tmp = root->right;
delete root;
return tmp;
}
if (!root->right) {
TreeNode* tmp = root->left;
delete root;
return tmp;
}
// 情况3：有两个孩子 —— 用右子树最小值替代
TreeNode* successor = findMin(root->right);
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
return root;
}3.5 考试常见考法
- ✅ 给定插入序列，画出 BST 并求中序遍历结果
- ✅ 选择题：BST 最坏情况退化为链表（有序插入时），查找时间复杂度 O(n)
- ✅ 给定 BST，删除某个节点后画出新树的结构
- ✅ 判断题：相同元素的不同插入顺序，得到的 BST 可能不同（✅正确）
四、哈夫曼编码（Huffman Coding）
4.1 前缀编码原理
前缀编码：任何字符的编码都不是另一个字符编码的前缀。这样可以保证解码时无歧义。
例如：A=0, B=10, C=110, D=111 —— 任意一个编码都不是另一个的前缀，合法 ✅
4.2 如何构造最优前缀编码
将哈夫曼树的左分支标记为 0，右分支标记为 1，从根到每个叶子节点的路径就是该字符的哈夫曼编码。
- 权值越大的字符，离根越近，编码越短
- 权值越小的字符，离根越远，编码越长
这就是哈夫曼编码的核心思想：出现频率高的字符用短编码，频率低的用长编码，从而整体编码最短。
4.3 计算压缩效率
压缩率 = 哈夫曼编码总长度 / 等长编码总长度 × 100%
节省比例 = (1 - 压缩率) × 100%示例：有字符 A(出现 50 次)、B(25 次)、C(15 次)、D(10 次)
等长编码（4个字符，每个 2 位）：总长度 = (50+25+15+10) × 2 = 200
假设哈夫曼编码为 A=0(1位)、B=10(2位)、C=110(3位)、D=111(3位)： 哈夫曼总长度 = 50×1 + 25×2 + 15×3 + 10×3 = 50 + 50 + 45 + 30 = 175
压缩率 = 175 / 200 = 87.5%，节省 12.5%
4.4 考试常见考法
- ✅ 给定字符频率，构造哈夫曼编码并计算 WPL
- ✅ 选择题：判断某组编码是否为合法的前缀编码
- ✅ 选择题：哈夫曼编码的平均长度一定 ≤ 等长编码的平均长度
- ✅ 计算题：给定报文长度和编码方案，求压缩效率
五、格雷编码（Gray Code）
5.1 定义
格雷码是一种循环码，其核心性质：相邻两个编码之间只有一位不同。
n 位格雷码共有 2^n 个编码。
5.2 生成规则（反射法 / 递归法）
递归构造：
| 位数 | 格雷码序列 |
|---|---|
| G(1) | 0, 1 |
| G(2) | 00, 01, 11, 10 |
| G(3) | 000, 001, 011, 010, 110, 111, 101, 100 |
构造方法（镜像反射法）：
- G(1) =
- G(n) = G(n-1) 的每个编码前补 0，然后接上 G(n-1) 逆序的每个编码前补 1
5.3 公式法（最高效）
第 n 个格雷码 = n XOR (n >> 1)
cpp
#include <iostream>
#include <vector>
using namespace std;
// 生成 n 位格雷码
vector<int> grayCode(int n) {
int total = 1 << n; // 2^n 个编码
vector<int> result;
for (int i = 0; i < total; i++) {
result.push_back(i ^ (i >> 1)); // 核心公式
}
return result;
}
int main() {
int n = 3;
vector<int> codes = grayCode(n);
for (int code : codes) {
// 输出 n 位二进制
for (int i = n - 1; i >= 0; i--) {
cout << ((code >> i) & 1);
}
cout << endl;
}
return 0;
}
// 输出：000 001 011 010 110 111 101 1005.4 考试常见考法
- ✅ 选择题：格雷码的核心特征——相邻编码仅一位不同
- ✅ 给定 n，要求写出 n 位格雷码序列
- ✅ 给定自然数 k，求其对应的格雷码（用公式 k ^ (k >> 1)）
- ✅ 格雷码的循环性：首尾两个编码也只有一位不同
六、高频易错点总结
| 知识点 | 易错点 |
|---|---|
| 哈夫曼树 | 没有度为 1 的节点；n 个叶子 → 2n-1 个节点；同一组权值，哈夫曼树不唯一（左右子树可交换），但 WPL 唯一 |
| 完全二叉树 | 编号从 1 开始；最后一层节点靠左连续；叶子节点只可能在最后两层 |
| 二叉排序树 | 最坏退化为链表（有序序列插入）；中序遍历 = 有序序列；删除有两孩子的节点时，用中序后继（或前驱）替代 |
| 哈夫曼编码 | 前缀编码的合法性判断；WPL 的计算方法；压缩效率公式 |
| 格雷编码 | 相邻仅一位不同 ≠ 任意两位都仅一位不同（只有相邻的才保证）；首尾也满足（循环码） |
七、📝 实战练习
练习题 1（编程题）
题目： 给定叶子节点权值集合 {3, 7, 2, 5, 9}，构造哈夫曼树，求 WPL。
🔑 点击查看答案与解析
解题过程：
- 初始：2, 3, 5, 7, 9，取 2 和 3，合并为 5，剩余 5, 5, 7, 9
- 取 5 和 5，合并为 10，剩余 7, 9, 10
- 取 7 和 9，合并为 16，剩余 10, 16
- 取 10 和 16，合并为 26，剩余 26
WPL = 5 + 10 + 16 + 26 = 57
也可以逐个叶子计算：9 的路径=2，7 的路径=2，5 的路径=2，3 的路径=3，2 的路径=3
WPL = 9x2 + 7x2 + 5x2 + 3x3 + 2x3 = 18 + 14 + 10 + 9 + 6 = 57
注意：实际构造过程中由于每次选最小的两个，具体树形可能不同，需要仔细逐步构造。
答案：WPL = 57
练习题 2（单选题）
题目： 依次插入序列 {30, 15, 45, 10, 20, 38, 50} 构造 BST，然后删除节点 30，画出删除后的 BST。
🔑 点击查看答案与解析
构造过程：
插入后 BST：
30
/ \
15 45
/ \ / \
10 20 38 50删除 30（有两个孩子）：
- 找右子树最小节点 = 38
- 用 38 替代 30 的位置，再删除原来的 38
删除后的 BST：
38
/ \
15 45
/ \ \
10 20 50答案：删除后根节点为 38，15 的左右孩子为 10 和 20，45 的右孩子为 50。
练习题 3（编程题）
题目： 求 3 位格雷码中，自然数 5 对应的格雷码是多少？
🔑 点击查看答案与解析
解题过程：
使用公式：格雷码 = n XOR (n >> 1)
5 的二进制 = 101
5 >> 1 = 010（即 2）
5 XOR 2 = 101 XOR 010 = 111（即 7）
验证：3 位格雷码序列为 000, 001, 011, 010, 110, 111, 101, 100 第 5 个（从 0 开始编号）确实为 111
答案：111（即十进制 7）
练习题 4（判断题）
题目： 哈夫曼树中没有度为 1 的节点。（ ）
🔑 点击查看答案与解析
答案： 正确 ✅
解析： 哈夫曼树的构造过程是每次选两个最小的节点合并，所以所有非叶子节点的度都是 2（有两个孩子），没有度为 1 的节点。
这也是哈夫曼树的一个重要性质：n 个叶子节点的哈夫曼树，总节点数 = 2n - 1。
验证：n 个叶子，每个新合并产生 1 个非叶子节点，共需合并 n-1 次，所以非叶子节点数 = n-1，总结点数 = n + (n-1) = 2n-1。
💡 记忆：哈夫曼树 = 严格二叉树（每个非叶子都有两个孩子）。
练习题 5（单选题）
题目： 一棵完全二叉树有 100 个节点，编号从 1 开始。编号为 50 的节点的左孩子编号是？（ ）
A. 25
B. 99
C. 100
D. 不存在
🔑 点击查看答案与解析
答案： C
解析： 完全二叉树数组存储的性质（编号从 1 开始）：
- 节点 i 的左孩子 = 2i
- 节点 i 的右孩子 = 2i + 1
- 节点 i 的父节点 = i / 2（向下取整）
节点 50 的左孩子 = 2 × 50 = 100
因为总节点数是 100，所以节点 100 存在。
选 C。
🔥 高频考点：完全二叉树的父子节点编号关系是选择题常客。注意：如果 2i > n，说明没有左孩子。
练习题 6（单选题）
题目： 二叉排序树的中序遍历结果是？（ ）
A. 升序序列
B. 降序序列
C. 随机序列
D. 前序序列
🔑 点击查看答案与解析
答案： A
解析： 二叉排序树（BST）的定义：左子树所有节点 < 根 < 右子树所有节点。
中序遍历顺序：左 → 根 → 右
所以中序遍历 BST 的结果是一个升序（从小到大）序列。
选 A。
💡 这是 BST 最重要的性质之一！判断一棵树是不是 BST，看中序遍历是不是升序就可以了。
练习题 7（单选题）
题目： 关于哈夫曼编码，下列说法错误的是？（ ）
A. 哈夫曼编码是前缀编码
B. 频率越高的字符，编码越短
C. 哈夫曼编码是唯一的
D. 哈夫曼树的 WPL 最小
🔑 点击查看答案与解析
答案： C
解析：
- A 正确 ✅：哈夫曼编码是前缀编码——任何一个编码都不是另一个编码的前缀，解码时不会有歧义
- B 正确 ✅：这正是哈夫曼编码的优势——用短编码表示高频字符，整体编码长度最短
- C 错误 ❌：哈夫曼树（和编码）不一定唯一！当有多个权值相同的节点时，选择哪两个合并、左右子树怎么分配，都可能导致不同的哈夫曼树，但 WPL 都是最小的
- D 正确 ✅：哈夫曼树就是带权路径长度最小的二叉树
选 C。
⚠️ 易错点：哈夫曼树不唯一，但 WPL 一定是唯一且最小的。
练习题 8（编程题）
题目： 在二叉排序树中删除一个节点有三种情况，请简述每种情况的处理方法。
- 要删除的节点是叶子节点
- 要删除的节点只有一个孩子
- 要删除的节点有两个孩子
🔑 点击查看答案与解析
答案：
叶子节点：直接删除，把父节点对应的指针设为空即可。
只有一个孩子：用孩子节点"接替"被删节点的位置。也就是让父节点直接指向这个孩子。
有两个孩子：找右子树中的最小值节点（或左子树中的最大值节点），用它的值替换被删节点的值，然后删除那个最小值节点（因为最小值节点一定没有左孩子，属于情况 1 或 2）。
解析： 删除有两个孩子的节点是最复杂的情况。核心思路是：找一个"替死鬼"——右子树最小值（或左子树最大值），它的值可以替换被删节点，同时保证 BST 性质不变。而那个替死鬼节点最多只有一个孩子，可以用前两种简单情况处理。
💡 记忆口诀：叶子直接删，一孩则孩子上，两孩找替代（右最左或左最右）。
八、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 哈夫曼树构造过程 | ⭐⭐⭐⭐⭐ | 选择/计算 | 每次选最小的两个合并 |
| WPL 计算 | ⭐⭐⭐⭐⭐ | 选择/计算 | 两种方法：权×深 或 非叶节点和 |
| 哈夫曼树特点（无度1节点） | ⭐⭐⭐⭐ | 选择/判断 | 总节点数 = 2n-1 |
| 哈夫曼编码（前缀编码） | ⭐⭐⭐⭐ | 选择/判断 | 左0右1；高频编码短 |
| 完全二叉树定义 | ⭐⭐⭐⭐ | 选择/判断 | 和满二叉树的关系 |
| 完全二叉树父子编号关系 | ⭐⭐⭐⭐⭐ | 选择/计算 | 左2i、右2i+1、父i/2 |
| 完全二叉树深度 | ⭐⭐⭐⭐ | 选择/计算 | floor(log2 n) + 1 |
| BST 定义（左小右大） | ⭐⭐⭐⭐⭐ | 选择/判断 | 注意是"所有"左子树节点都小 |
| BST 中序遍历 = 升序 | ⭐⭐⭐⭐⭐ | 选择/程序阅读 | 高频考点，必须记住 |
| BST 删除操作 | ⭐⭐⭐⭐ | 选择/代码填空 | 两孩情况找替代 |
| 格雷码生成公式 | ⭐⭐⭐ | 选择/计算 | G(n) = n XOR (n>>1) |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 哈夫曼树与特殊树 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. 哈夫曼树：每次合最小，WPL最小 │
│ 2. WPL = 各叶子权×深度之和 │
│ 3. WPL = 所有非叶子节点权值之和 │
│ 4. 哈夫曼树没有度为1的节点 │
│ 5. n个叶子的哈夫曼树，总结点数 = 2n-1 │
│ 6. 哈夫曼编码是前缀编码，左0右1 │
│ 7. 哈夫曼树不唯一，但WPL唯一最小 │
│ 8. 完全二叉树：前k-1层满，最后一层左连续 │
│ 9. 完全二叉树左孩子=2i，右孩子=2i+1 │
│ 10. 完全二叉树父节点=i/2（向下取整） │
│ 11. BST二叉排序树：左小右大 │
│ 12. BST中序遍历 = 升序序列 │
│ 13. BST删除：叶直接删，一孩则孩子接 │
│ 14. BST两孩删除：右最左（或左最右）来替代 │
│ 15. 格雷码：G(n) = n XOR (n右移1位) │
└─────────────────────────────────────────────┘