竞极 Ace

6 二叉树进阶与哈夫曼树

GESP C++ 六级：二叉树进阶与哈夫曼树

核心目标：在掌握二叉树基础与遍历的前提下，深入理解完全二叉树、二叉排序树、哈夫曼树三种特殊二叉树的结构特性与典型应用，掌握哈夫曼树的构造方法、WPL计算与哈夫曼编码的生成规则，能辨析相关选择题与程序阅读题。
完全二叉树靠数组顺序存储，下标关系固定；二叉排序树靠“左小右大”实现高效查找；哈夫曼树靠“每次合并最小两个”实现WPL最小，编码靠“左0右1”得到前缀码——频率高的字符离根近、编码短。

一、考纲定位

根据 CCF 官方考纲，六级知识内容明确包含：“树的定义，构造与遍历；哈夫曼树、完全二叉树、二叉排序树；哈夫曼编码”。其中哈夫曼树与哈夫曼编码是六级数据结构模块的高频考点，在选择题和程序阅读题中反复出现。

六级二叉树进阶的考查分布：

考点 重要程度 典型考法
完全二叉树的判断与下标计算 ★★★★★ 选择题、编程题
二叉排序树的插入/查找/中序性质 代码填空、程序阅读
哈夫曼树的构造过程 选择题、代码填空
WPL（带权路径长度）计算 选择题、计算题
哈夫曼编码的生成与辨析 选择题高频
哈夫曼树合并节点归属 ★★★★☆ 代码填空、程序阅读

六级二叉树进阶的命题趋势是：不考孤立的定义背诵，而是考“过程中的细节” ——构造哈夫曼树时新节点放在哪个队列、合并后权值如何计算、编码是否满足前缀性质、二叉排序树中序遍历为什么有序。理解过程比记住结论更重要。

二、完全二叉树进阶

2.1 完全二叉树的判定

完全二叉树的条件：除最后一层外，其他层都是满的；最后一层的节点全部集中在左侧。

遍历判定法（层序遍历，队列实现）：

bool isCompleteTree(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;   // 是否遇到过空孩子

    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();

        if (node == nullptr) {
            hasNull = true;      // 遇到空，之后不能再有非空
        } else {
            if (hasNull) return false;   // 空之后又出现非空，不是完全二叉树
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

核心逻辑：层序遍历过程中，一旦遇到空节点，后续不能再出现非空节点。空节点之后如果还有非空节点，说明节点没有集中在左侧，不是完全二叉树。

2.2 顺序存储的下标关系（必记）

完全二叉树最适合用数组顺序存储。根节点下标为 1 时：

关系 公式 示例（根下标1）
左孩子 2 * i 下标2的节点，左孩子下标4
右孩子 2 * i + 1 下标2的节点，右孩子下标5
父节点 i / 2 下标5的父节点下标2
是否为叶子 2 * i > n 下标3，左孩子6，若n=5则3是叶子

真题示例：一棵完全二叉树按顺序存储，根节点下标为 1，则下标为 5 的节点的左孩子下标是（ ）。答案：10（2 * 5 = 10）。

如果根节点下标为 0，关系变为：左孩子 2*i+1，右孩子 2*i+2，父节点 (i-1)/2。考试中一定要看清题目给定的根下标是 0 还是 1。

2.3 完全二叉树的节点数关系

条件 公式
第 i 层最多节点数 2i−12^{i-1}（根为第1层）
深度为 h 的完全二叉树，节点数范围 2h−12^{h-1} ~ 2h−12^h - 1
叶子节点数（完全二叉树） 当 n 为偶数：n/2；当 n 为奇数：(n+1)/2

三、二叉排序树（BST）

3.1 核心性质

二叉排序树（Binary Search Tree）满足：左子树所有节点值 < 根节点值 < 右子树所有节点值。空树和单节点树也是合法的二叉排序树。

最关键的性质：二叉排序树的中序遍历结果是一个严格递增的有序序列。这个性质是 BST 所有查找类操作的基础，也是高频选择题考点。

3.2 BST 的查找

TreeNode* search(TreeNode* root, int target) {
    if (root == nullptr || root->val == target) return root;
    if (target < root->val)
        return search(root->left, target);
    else
        return search(root->right, target);
}

核心逻辑：target 小于当前节点值就往左走，大于就往右走，等于就返回。

3.3 BST 的插入

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val)
        root->left = insert(root->left, val);
    else
        root->right = insert(root->right, val);
    return root;
}

真题示例（2025年3月六级第5题） ：

以下代码实现了二叉排序树的哪种操作？

TreeNode* op(TreeNode* root, int val) {
 if (root == nullptr) return new TreeNode(val);
 if (val < root->val) root->left = op(root->left, val);
 else root->right = op(root->right, val);
 return root;
}

答案：B（插入） 。代码在空位置创建新节点并挂到父节点上，是标准的 BST 插入操作。

3.4 BST 的删除（了解）

删除节点分三种情况：

  1. 叶子节点：直接删除。
  2. 只有一个孩子：用孩子替换被删节点。
  3. 有两个孩子：用右子树的最小节点（或左子树的最大节点）替换，再删除那个最小节点。

四、哈夫曼树

4.1 核心概念

哈夫曼树（Huffman Tree）是一棵带权路径长度（WPL）最短的二叉树，又称最优二叉树。

几个关键定义：

概念 定义
路径长度 从根到某节点经过的边数
节点的带权路径长度 该节点的权值 × 从根到该节点的路径长度
树的带权路径长度（WPL） 所有叶子节点的带权路径长度之和
哈夫曼树 WPL 最小的二叉树

WPL 的计算公式：

WPL=∑i=1nwi×di \text{WPL} = \sum_{i=1}^{n} w_i \times d_i

其中 wiw_i 是第 i 个叶子节点的权值，did_i 是该叶子节点的深度（从根到该叶子的边数）。

注意：WPL 只计算叶子节点，不计算内部节点。内部节点的权值只是构造过程中的“中间产物”。

4.2 构造过程（必考）

哈夫曼树的构造采用贪心策略，核心规则是：每次选择权值最小的两个节点合并。

构造步骤：

1. 将所有权值看作独立的树（森林），每棵树只有一个节点
2. 从森林中选择权值最小的两棵树 T1 和 T2
3. 合并：新建一个内部节点，权值 = T1权值 + T2权值
       T1 作为左孩子，T2 作为右孩子（或反之，左右不影响WPL）
4. 将新节点放回森林，删除 T1 和 T2
5. 重复步骤2-4，直到森林中只剩一棵树

n 个叶子节点的哈夫曼树共有 2n-1 个节点（n 个叶子 + n-1 个内部节点），需要 n-1 次合并。

4.3 构造示例

给定权值 {5, 1, 6, 2}，构造哈夫曼树：

第1次合并：选最小两个 1 和 2，合并为 3。
第2次合并：选最小两个 3 和 5，合并为 8。
第3次合并：选最小两个 6 和 8，合并为 14（根）。

        14
       /  \
      6    8
          / \
         3   5
        / \
       1   2

WPL 计算（只算叶子）：

  • 6 的深度为 1：6 × 1 = 6
  • 5 的深度为 2：5 × 2 = 10
  • 1 的深度为 3：1 × 3 = 3
  • 2 的深度为 3：2 × 3 = 6

WPL = 6 + 10 + 3 + 6 = 25

4.4 真题精讲：合并节点的归属（2025年12月六级第8题）

在哈夫曼树构造过程中，合并两个最小节点后产生的新节点应该（ ）。
A. 放入内部节点队列（internalIdx）
B. 放入叶子节点队列（leafIdx）
C. 直接作为根节点
D. 丢弃
答案：A

解析：哈夫曼算法的核心流程中，合并产生的新节点是一个内部节点（不是原始字符），它的权值是两个孩子权值之和。这个新节点必须放回内部节点队列，参与后续的合并，而不是放回叶子队列（叶子队列只存放最初的字符节点）。

记忆口诀：叶子队列只放最初的字符，合并出来的节点都是内部节点，放内部队列。

五、哈夫曼编码

5.1 编码规则

从哈夫曼树的根出发：向左分支记 0，向右分支记 1。从根到某个叶子节点的路径上，0/1 序列就是这个叶子对应字符的哈夫曼编码。

左右互换不影响编码的最优性（WPL 不变），但会产生不同的具体编码。

5.2 哈夫曼编码的两个核心性质

性质 含义 为什么重要
变长编码 频率高的字符编码短，频率低的字符编码长 压缩效果
前缀编码 任何一个字符的编码都不是另一个字符编码的前缀 保证唯一解码

前缀性质的含义：解码时不需要分隔符，从根开始逐位匹配，遇到叶子就输出一个字符，不会产生歧义。例如 A: 0，B: 10，C: 11 是合法的前缀码；而 A: 0，B: 01 则不是（0 是 01 的前缀，解码时遇到 0 无法确定是 A 还是 B 的一部分）。

5.3 真题精讲：编码辨析（2025年3月六级第6题）

给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2}，则正确的哈夫曼编码是（ ）。
A. A: 0, B: 100, C: 11, D: 101
B. A: 11, B: 100, C: 0, D: 101
C. A: 0, B: 101, C: 11, D: 100
D. A: 10, B: 101, C: 0, D: 100
答案：A

解析：频率 C(6) 最高，编码应该最短（1位）；A(5) 次之，编码应该较短（1位或2位）；B(1) 和 D(2) 最低，编码应该最长（3位）。A 选项中 C 是 11（2位），A 是 0（1位），B 和 D 是 3位，整体编码长度分配合理，且满足前缀性质。B 选项中 C 的编码是 0（1位），但 A 的编码是 11（2位），A 的频率 5 比 D 的频率 2 高，A 的编码不应比 D 长太多；更重要的是，B 选项中 A: 11，D: 101，D 的编码以 1 开头，与 A 的 11 不构成前缀冲突，但 B 和 D 的频率最低却编码最长，分配逻辑不够优化。判断哈夫曼编码是否正确，核心是看频率与编码长度的对应关系是否合理，以及是否满足前缀性质。

5.4 真题精讲：哈夫曼编码的错误描述（2025年3月六级第2题）

以下关于哈夫曼编码的描述中，不正确的是（ ）。
A. 哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。
B. 在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。
C. 哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。
D. 哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀。
答案：B

解析：B 选项说反了。哈夫曼树中，频率越低的字符离根越远，频率越高的字符离根越近。频率高 → 编码短 → 离根近；频率低 → 编码长 → 离根远。这是哈夫曼编码压缩效果的核心来源。

5.5 真题精讲：哈夫曼编码的正确说法（2025年12月六级第9题）

关于哈夫曼编码，哪个说法是正确的？
A. 哈夫曼编码是定长编码
B. 哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀
C. 哈夫曼编码只能用于文本压缩
D. 哈夫曼树是唯一的
答案：B

解析：A 错，哈夫曼是变长编码；C 错，也可用于图像、音频压缩；D 错，当出现相同权值时，合并顺序不同可能产生不同形状的哈夫曼树（但 WPL 相同），因此哈夫曼树不唯一，但 WPL 唯一。B 正确，这是前缀编码的核心性质。

六、二叉树进阶综合真题精讲

真题1：完全二叉树判断代码（2025年3月六级第4题）

以下代码用于判断一棵树是否为（ ）。

bool isCompleteTree(TreeNode* root) {
 if (!root) return true;
 queue<TreeNode*> q;
 q.push(root);
 bool hasNull = false;
 while (!q.empty()) {
     TreeNode* node = q.front(); q.pop();
     if (node == nullptr) {
         hasNull = true;
     } else {
         if (hasNull) return false;
         q.push(node->left);
         q.push(node->right);
     }
 }
 return true;
}

A. 满二叉树 B. 完全二叉树 C. 二叉搜索树 D. 计算树的高度
答案：B

解析：代码使用层序遍历，一旦遇到空节点就标记 hasNull = true，之后如果再遇到非空节点就返回 false。这正是完全二叉树的判定逻辑：节点必须集中在左侧，不能出现“空节点之后还有非空节点”的情况。

真题2：二叉排序树搜索填空（2024年3月六级第5题）

在 BST 搜索代码的横线处填入（ ）。

TreeNode* search(TreeNode* root, int target) {
 if (root == NULL || root->val == target) return root;
 if (_______________) return search(root->left, target);
 else return search(root->right, target);
}

A. target < root->left
B. target < root->val
C. target > root->val
D. target > root->left
答案：B

解析：BST 的性质是左子树所有值 < 根 < 右子树所有值。当 target < root->val 时，说明目标在左子树中，应递归搜索左子树。

真题3：哈夫曼树合并选择（2024年3月六级第1题）

在构建哈夫曼树时，每次应该选择（ ）合并。
A. 最小权值的节点
B. 最大权值的节点
C. 随机节点
D. 深度最深的节点
答案：A

解析：哈夫曼树的目标是让 WPL 最小。每次选择权值最小的两个节点合并，可以让权值小的节点离根更远（路径更长），权值大的节点离根更近（路径更短），从而最小化“权值 × 路径长度”的总和。

七、易错点汇总

  1. WPL 只计算叶子节点：内部节点的权值是中间产物，不计入 WPL。
  2. 深度与层数混淆：WPL 公式中的深度是从根到叶子的边数。根到孩子的深度为 1，不是 0。如果题目把根定义为第 1 层，深度 = 层数 − 1。
  3. 哈夫曼树不唯一，但 WPL 唯一：当出现相同权值时，合并顺序可能不同，树形不同，但 WPL 一定相同。
  4. 哈夫曼编码是变长编码，不是定长编码：高频错误选项。
  5. 频率高的字符离根近，不是远：这是最高频的反向陷阱。
  6. 完全二叉树判定中“空之后不能再有非空” ：这是核心逻辑，写代码时不能漏。
  7. BST 中序遍历有序：这是 BST 所有查找操作的基础，选择题常考“BST 的中序遍历结果是什么”。
  8. 顺序存储根下标 0 和 1 的关系式不同：根下标 1 时左孩子 2i，根下标 0 时左孩子 2i+1，考试中要看清题目约定。
  9. 哈夫曼构造的合并次数是 n-1：n 个叶子节点需要 n-1 次合并，最终产生 2n-1 个节点。
  10. 哈夫曼编码的左右分支可以互换：左右互换不影响最优性，但会产生不同的具体编码，因此“编码结果唯一”是错误的。

八、速查表

需求 公式/方法 关键注意
完全二叉树判定 层序遍历 + hasNull 标记 空之后不能再有非空
顺序存储（根1） 左 2i，右 2i+1，父 i/2 看清根下标约定
顺序存储（根0） 左 2i+1，右 2i+2，父 (i-1)/2 与根1不同
BST 查找 target < root->val 走左，否则走右 中序遍历有序
BST 插入 空位置创建新节点 递归挂接
哈夫曼构造 每次合并最小两个节点 n-1 次合并
WPL 计算 ∑wi×di\sum w_i \times d_i，只算叶子 深度 = 边数
哈夫曼编码规则 左 0，右 1 前缀码，保证唯一解码
频率与编码长度 频率高 → 编码短 → 离根近 高频反向陷阱
哈夫曼树节点数 2n - 1（n 个叶子） 内部节点 n-1 个
合并节点归属 内部节点队列 不放叶子队列

九、总结

二叉树进阶与哈夫曼树是 GESP 六级数据结构模块的核心内容。

  1. 完全二叉树的判定靠层序遍历：空节点之后不能再出现非空节点。
  2. 完全二叉树顺序存储：根下标 1 时左孩子 2i，根下标 0 时左孩子 2i+1。
  3. 二叉排序树的核心性质是中序遍历有序，查找靠“左小右大”。
  4. 哈夫曼树是 WPL 最小的二叉树，构造时每次合并权值最小的两个节点。
  5. WPL 只计算叶子节点的“权值 × 深度”，内部节点不计入。
  6. n 个叶子节点的哈夫曼树有 2n−1 个节点，需要 n−1 次合并。
  7. 哈夫曼编码是变长编码，频率高的字符编码短、离根近。
  8. 哈夫曼编码是前缀编码，任何编码都不是其他编码的前缀。
  9. 哈夫曼树不唯一，但 WPL 唯一；左右互换不影响最优性。
  10. 多练“完全二叉树判断代码”“BST 查找填空”“哈夫曼编码辨析”“WPL 计算”四类题。

复习建议：先把完全二叉树和 BST 的核心性质记熟，重点理解“中序遍历有序”和“层序判定完全”两个核心逻辑；再动手模拟哈夫曼树的构造过程，从 {5,1,6,2} 这类小例子开始，每一步都写出合并后的森林状态和最终 WPL；然后练习哈夫曼编码的生成与辨析，重点区分“频率高离根近”和“前缀码”两个易错点；最后用 2025 年 3 月和 12 月的真题做限时训练，查漏补缺。考试中先判断题目考的是哪种特殊二叉树，再套用对应的性质或构造规则，最后检查细节（WPL 是否只算叶子、顺序存储根下标是 0 还是 1、编码是否满足前缀性质）。