Day 12　树的遍历与哈夫曼树

建议用时：22～28 分钟
今日目标：分清前序、中序、后序和层序遍历，会由遍历序列分析树形，并掌握哈夫曼树的合并过程与带权路径长度。

大纲定位：二叉树前序/中序/后序遍历、完全二叉树相关性质、哈夫曼树构造与哈夫曼编码。

一、遍历不是“看一眼”，而是规定访问次序

遍历的目标是让每个结点都被访问一次。对任意一棵非空二叉树，都可以先把它看成三个部分：根、左子树、右子树。三种深度优先遍历的差别只在于根什么时候被访问：

• 前序遍历：根 → 左子树 → 右子树；
• 中序遍历：左子树 → 根 → 右子树；
• 后序遍历：左子树 → 右子树 → 根。

这里的“左子树”不是只访问左孩子，而是把整棵左子树按照同一种规则递归走完。做题时可以在每个结点旁画三个小点：第一次到达结点时记录是前序点，从左子树回来时是中序点，准备离开结点时是后序点。

例如：

        A
       / \
      B   C
     / \   \
    D   E   F

• 前序：A B D E C F
• 中序：D B E A C F
• 后序：D E B F C A

层序遍历则从上到下、同层从左到右访问。实现时先把根放进队列；每次取出队首结点，再把它存在的左右孩子依次入队。因此层序遍历使用队列，不是栈。

二、读递归遍历程序：先找输出语句的位置

典型代码只有三行核心操作：

walk(left[u]);
cout << u;
walk(right[u]);

输出放在两次递归之间，所以是中序。若移到第一行之前就是前序，移到第二次递归之后就是后序。若代码先递归右子树，再递归左子树，顺序就相应变成“右—根—左”等，不能仍套“左根右”。

阅读递归时不要试图同时记住整棵树。写一个调用栈小表：当前结点是谁、即将执行左递归/输出/右递归中的哪一步。遇到 u==0 立即返回，不会产生输出。

三、由遍历序列还原二叉树

当所有结点标号互不相同时：

• 前序的第一个结点一定是根；
• 后序的最后一个结点一定是根；
• 在中序中找到根，左边全部属于左子树，右边全部属于右子树。

以本页示例为例，前序为 A B D E C F，中序为 D B E A C F：

1. 前序首项 A 是根；
2. 中序在 A 左边有 D B E，所以左子树有 3 个结点；右边 C F 属于右子树；
3. 前序紧随 A 的 3 项 B D E 就是左子树的前序，剩余 C F 是右子树前序；
4. 对左右两部分重复同样过程，得到 B 的左右孩子 D、E，C 的右孩子 F。

因此“前序 + 中序”或“中序 + 后序”通常可以唯一确定一棵结点互异的二叉树。前序和后序都只能告诉我们根的位置：当某个结点只有一个孩子时，无法判断它是左孩子还是右孩子，所以一般不能唯一还原。

四、路径长度、权值与 WPL

从根到某结点经过的边数叫该结点的路径长度。根的路径长度为 0，根的孩子为 1。若叶子 i 的权值为 w_i、路径长度为 l_i，整棵树的带权路径长度为

权值可以理解为字符出现次数：出现越频繁的字符若放得越靠近根，编码总长度就越短。哈夫曼树正是在给定叶子权值时，使 WPL 最小的二叉树。

注意 WPL 只统计带权叶子，不是把所有结点的权值简单相加，也不是树上所有边数。

五、哈夫曼树：每轮只合并最小的两个

构造过程像一场“淘汰赛”：

1. 从当前集合取最小的两个权值；
2. 用它们作为两个孩子，父结点权值为二者之和；
3. 把新权值放回集合并重新排序；
4. 重复到集合只剩一个权值。

以 5,7,10,15,20 为例：

所有合并值之和就是

原因是：每合并一次，这两个子树里所有叶子的深度都增加 1，它们增加的总贡献恰好等于新结点的权值。

若出现相同权值，具体树形可能不唯一，但最小 WPL 相同。左右孩子交换也不会改变 WPL。

六、哈夫曼编码为什么不会读串

给哈夫曼树左边标 0、右边标 1（反过来也可以），从根走到某个叶子的路径就得到该字符编码。只有叶子代表字符，因此任何字符编码都不会成为另一个字符编码的前缀，这叫前缀编码。

例如若某字符编码是 01，那么其他字符就不能再使用 010，否则读到 01 时无法判断应该立即结束还是继续读取。前缀编码可以从左到右唯一解码，不需要额外分隔符。

2021、2022、2023、2025 年 CSP-J 单选题都出现过树遍历、完全二叉树或哈夫曼相关考点。常见失分点不是不会背“每次取最小”，而是合并后忘记把新权值放回并重新参与比较。

今日练习

第 1～6 题全部来自 2021～2025 年 CSP-J 第一轮单选；第 7、8 题继续用短程序检查遍历理解。

1. 【CSP-J 2021·第 11 题】 数据压缩编码中的哈夫曼编码，本质上采用（　）策略。

   A. 枚举　 B. 贪心　 C. 递归　 D. 动态规划

2. 【CSP-J 2022·第 7 题】 字母 {a,b,c,d,e} 的出现频率依次为 10%,15%,30%,16%,29%。使用哈夫曼编码时，字母 d 的编码长度为（　）位。

   A. 1　 B. 2　 C. 2 或 3　 D. 3

3. 【CSP-J 2023·第 10 题】 字符 {a,b,c,d,e,f} 的频率依次为 5%,9%,12%,13%,16%,45%。下列哪一组分别对应一组合法的哈夫曼编码？（　）

   A. 1111，1110，101，100，110，0
   B. 1010，1001，1000，011，010，00
   C. 000，001，010，011，10，11
   D. 1010，1011，110，111，00，01

4. 【CSP-J 2023·第 11 题】 一棵二叉树的前序遍历为 ABDECFG，中序遍历为 DEBACFG，其后序遍历为（　）。

   A. EDBFGCA　 B. EDBGCFA　 C. DEBGFCA　 D. DBEGFCA

5. 【CSP-J 2024·第 12 题】 已知二叉树的前序遍历为 [A,B,D,E,C,F,G]，中序遍历为 [D,B,E,A,F,C,G]，其后序遍历为（　）。

   A. DEBFGCA　 B. DEBFGAC　 C. DBEFGCA　 D. DEBFGAC

6. 【CSP-J 2025·第 4 题】 用权值 10,12,15,20,25 构造哈夫曼树，该树的带权路径长度是（　）。

   A. 176　 B. 186　 C. 196　 D. 206

主题程序阅读

阅读下面的程序：

#include <iostream>
using namespace std;

int lc[7] = {0, 2, 4, 0, 0, 0, 0};
int rc[7] = {0, 3, 5, 6, 0, 0, 0};

void walk(int u) {
    if (u == 0) return;
    walk(lc[u]);
    cout << u << ' ';
    walk(rc[u]);
}

int main() {
    walk(1);
    return 0;
}

7. 若把 cout << u << ' '; 移到第一次递归调用之前，输出将变成 1 2 4 5 3 6。（判断对错）

8. 若交换 walk(lc[u]); 与 walk(rc[u]); 的位置，输出将变成 6 3 1 5 2 4。（判断对错）

#include <iostream>
using namespace std;

int lc[7] = {0, 2, 4, 0, 0, 0, 0};
int rc[7] = {0, 3, 5, 6, 0, 0, 0};

void walk(int u) {
    if (u == 0) return;
    walk(lc[u]);
    cout << u << ' ';
    walk(rc[u]);
}

int main() {
    walk(1);
    return 0;
}