Lesson 36: 二叉树 DFS 遍历
练习任务
难度: 易-中 【重点】
实现二叉树的三种递归遍历函数--preorder(root)(前序)、inorder(root)(中序)、postorder(root)(后序)。二叉树已由 build_tree 函数按层序 token 流(. 表示空节点)构建好,make_node 已提供。三种遍历的递归结构完全相同--唯一的区别是 printf(访问根节点)的位置。
本课共有 2 组测试用例:
输入 "A B C . . ." -> preorder: A B C
inorder: B A C
postorder: B C A
输入 "A . ." -> preorder: A
inorder: A
postorder: A提示: 三种遍历的代码几乎一模一样,只差一行
printf的顺序。记忆口诀--前序 = 根在最前面(根->左->右),中序 = 根在正中间(左->根->右),后序 = 根在最后面(左->右->根)。每一个遍历函数的第一行必须是if (root == NULL) return;--这是递归树的终止条件,也是树的递归定义在代码中的直接体现。
核心知识点
- 二叉树的递归定义--树 = 根 + 左子树 + 右子树,
struct node结构体、NULL表示空子树 - 前/中/后序遍历的递归模型--三种遍历只有
printf位置不同(根左右 / 左根右 / 左右根) root == NULL终止条件--空树是递归终止,与数学中树的递归定义同构- 中序遍历 BST = 有序序列--BST 区别于普通二叉树的"指纹"特性
- 前序首元素 = 根,后序末元素 = 根--遍历序列与树结构的对应关系
- 前序 + 中序(或后序 + 中序)唯一重构二叉树--前序 + 后序不能唯一确定
- 非递归栈遍历--手动维护显式栈模拟递归,避免递归调用栈溢出
- Morris 遍历--O(1) 额外空间的非递归遍历,利用空闲指针线索化
- 应用场景映射--序列化(前序)、BST 排序(中序)、安全释放(后序)
代码框架
c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char ch;
struct node *left, *right;
};
struct node *make_node(char ch) {
struct node *p = malloc(sizeof(*p));
p->ch = ch;
p->left = p->right = NULL;
return p;
}
/* 按层序构建二叉树:token 流,'.' 表示空节点 */
struct node *build_tree(char *tokens) {
// 已提供:用队列 BFS 构建,处理 '.' 为 NULL
// 在这里实现 build_tree...
// 请实现以下三个遍历函数
}
/* 前序遍历:根 -> 左 -> 右 */
void preorder(struct node *root) {
// 在这里实现 preorder:
// 1. if (root == NULL) return;
// 2. printf("%c ", root->ch);
// 3. preorder(root->left);
// 4. preorder(root->right);
}
/* 中序遍历:左 -> 根 -> 右 */
void inorder(struct node *root) {
// 在这里实现 inorder:
// 1. if (root == NULL) return;
// 2. inorder(root->left);
// 3. printf("%c ", root->ch);
// 4. inorder(root->right);
}
/* 后序遍历:左 -> 右 -> 根 */
void postorder(struct node *root) {
// 在这里实现 postorder:
// 1. if (root == NULL) return;
// 2. postorder(root->left);
// 3. postorder(root->right);
// 4. printf("%c ", root->ch);
}
int main(void) {
char line[256];
fgets(line, sizeof(line), stdin);
struct node *root = build_tree(line);
printf("preorder: ");
preorder(root);
printf("\n");
printf("inorder: ");
inorder(root);
printf("\n");
printf("postorder: ");
postorder(root);
printf("\n");
return 0;
}阅读骨架后,思考:三个函数的代码几乎一模一样--为什么输出序列完全不同?printf 放在递归调用前、中、后分别意味着什么?root == NULL 为什么是递归的第一行?
TIP
先不要往下翻看参考解答。画一棵 3 个节点的小树(A 为根、B 为左孩子、C 为右孩子),用纸笔手动追踪三种遍历的递归调用过程。你会发现:三种遍历访问的路径完全相同,只是打印节点的时机不同。
深度讲解
1. 二叉树的数据结构与递归定义
1.1 struct node--树的物理表示
c
struct node {
char ch; // 节点存储的字符
struct node *left; // 指向左子树的指针
struct node *right; // 指向右子树的指针
};一个节点的内存布局:
+-------------+
root ->| ch = 'A' |
+-------------+
| left ------------> 左子树(可以是另一个 node 或 NULL)
+-------------+
| right ------------> 右子树(可以是另一个 node 或 NULL)
+-------------+每个节点存储三个字段:数据 ch、左孩子指针 left、右孩子指针 right。NULL 表示空子树--这是递归的终止条件。
c
struct node *make_node(char ch) {
struct node *p = malloc(sizeof(*p));
p->ch = ch;
p->left = p->right = NULL; // 叶子节点:左右子树都为空
return p;
}1.2 树的递归定义--为什么递归遍历如此自然
数学上,二叉树的定义本身是递归的:
一棵二叉树要么是空树(NULL),要么由根节点、左子树、右子树组成,其中左子树和右子树本身也是二叉树。
树 = 空树 | (根 + 左子树 + 右子树)
根
/ \
左 右 <- 左子树和右子树本身也是二叉树!
/ \ / \
... ... ...代码中,这个递归定义直接映射为:
c
// 树的递归定义在代码中的体现:
// 空树 -> root == NULL
// 根 -> root(当前节点)
// 左子树 -> root->left(也是 struct node*,递归处理)
// 右子树 -> root->right(也是 struct node*,递归处理)这解释了为什么递归遍历二叉树如此自然--树的定义是递归的,处理树的函数也是递归的。二者在结构上完全同构。
1.3 树的术语速查
A <- 根节点 (root),深度 0
/ \
B C <- A 的孩子,深度 1
/ \ \
D E F <- 深度 2
/ \
G H <- 叶子节点:无孩子的节点 (E, F, G, H)
术语:
+----------------------------------------------------------+
| 根节点 (root): 树的最顶层节点 (A) |
| 叶子节点 (leaf): 无孩子的节点 (E, F, G, H) |
| 父节点 (parent): 有孩子的节点 (A 是 B/C 的父) |
| 子树 (subtree): 以某节点为根的树 (以 B 为根的子树 |
| 包含 B, D, E, G, H) |
| 深度 (depth): 从根到该节点的边数 (根深度 0) |
| 高度 (height): 从该节点到最深叶子的边数 |
+----------------------------------------------------------+2. 三种遍历的递归模型
2.1 口诀--三种遍历的唯一区别
三种遍历的递归框架完全相同,唯一区别是 printf 的位置:
/* 前序 Pre-order :根 -> 左 -> 右 (根在最前面!) */
void preorder(struct node *root) {
if (root == NULL) return; // (1) 终止条件
printf("%c ", root->ch); // (2) 先访问根
preorder(root->left); // (3) 递归左子树
preorder(root->right); // (4) 递归右子树
}
/* 中序 In-order :左 -> 根 -> 右 (根在正中间!) */
void inorder(struct node *root) {
if (root == NULL) return;
inorder(root->left); // (1) 先递归左子树
printf("%c ", root->ch); // (2) 访问根(在中间)
inorder(root->right); // (3) 递归右子树
}
/* 后序 Post-order:左 -> 右 -> 根 (根在最后面!) */
void postorder(struct node *root) {
if (root == NULL) return;
postorder(root->left); // (1) 先递归左子树
postorder(root->right); // (2) 递归右子树
printf("%c ", root->ch); // (3) 最后访问根
}记忆口诀:
| 遍历 | 顺序 | 口诀 | 根的位置 |
|---|---|---|---|
| 前序 (Pre) | 根->左->右 | 根左右 | 最前 |
| 中序 (In) | 左->根->右 | 左根右 | 中间 |
| 后序 (Post) | 左->右->根 | 左右根 | 最后 |
NOTE
"前/中/后"描述的是根节点被访问的时机--前序最先访问根,中序中间访问根,后序最后访问根。三种遍历访问的路径(走过的边)完全相同,区别只在何时打印。
2.2 以一棵完整树为例--三种遍历的完整追踪
A
/ \
B C
/ \ \
D E F
/ \
G H
前序 (根左右): A B D G H E C F
中序 (左根右): G D H B E A C F
后序 (左右根): G H D E B F C A前序遍历:A -> B -> D -> G -> H -> E -> C -> F
执行过程(缩进表示递归层次):
preorder(A)
+-- visit(A) -> 输出 "A " // 根在最前
+-- preorder(B)
| +-- visit(B) -> 输出 "B "
| +-- preorder(D)
| | +-- visit(D) -> 输出 "D "
| | +-- preorder(G)
| | | +-- visit(G) -> 输出 "G "
| | | +-- preorder(NULL) -> return
| | | +-- preorder(NULL) -> return
| | +-- preorder(H)
| | +-- visit(H) -> 输出 "H "
| | +-- preorder(NULL) -> return
| | +-- preorder(NULL) -> return
| +-- preorder(E)
| +-- visit(E) -> 输出 "E "
| +-- preorder(NULL) -> return
| +-- preorder(NULL) -> return
+-- preorder(C)
+-- visit(C) -> 输出 "C "
+-- preorder(NULL) -> return
+-- preorder(F)
+-- visit(F) -> 输出 "F "
+-- preorder(NULL) -> return
+-- preorder(NULL) -> return
输出: A B D G H E C F中序遍历:G -> D -> H -> B -> E -> A -> C -> F
执行过程:
inorder(A)
+-- inorder(B)
| +-- inorder(D)
| | +-- inorder(G)
| | | +-- inorder(NULL) -> return
| | | +-- visit(G) -> 输出 "G " // 左叶子在最前面!
| | | +-- inorder(NULL) -> return
| | +-- visit(D) -> 输出 "D "
| | +-- inorder(H)
| | +-- inorder(NULL) -> return
| | +-- visit(H) -> 输出 "H "
| | +-- inorder(NULL) -> return
| +-- visit(B) -> 输出 "B " // B 在 D 之后(中序!)
| +-- inorder(E)
| +-- inorder(NULL) -> return
| +-- visit(E) -> 输出 "E "
| +-- inorder(NULL) -> return
+-- visit(A) -> 输出 "A " // 根在正中间!
+-- inorder(C)
+-- inorder(NULL) -> return
+-- visit(C) -> 输出 "C "
+-- inorder(F)
+-- inorder(NULL) -> return
+-- visit(F) -> 输出 "F "
+-- inorder(NULL) -> return
输出: G D H B E A C F后序遍历:G -> H -> D -> E -> B -> F -> C -> A
执行过程:
postorder(A)
+-- postorder(B)
| +-- postorder(D)
| | +-- postorder(G)
| | | +-- postorder(NULL) -> return
| | | +-- postorder(NULL) -> return
| | | +-- visit(G) -> 输出 "G " // 叶子最先打印
| | +-- postorder(H)
| | | +-- postorder(NULL) -> return
| | | +-- postorder(NULL) -> return
| | | +-- visit(H) -> 输出 "H "
| | +-- visit(D) -> 输出 "D " // D 在 G、H 之后
| +-- postorder(E)
| | +-- postorder(NULL) -> return
| | +-- postorder(NULL) -> return
| | +-- visit(E) -> 输出 "E "
| +-- visit(B) -> 输出 "B " // B 在 D、E 之后
+-- postorder(C)
| +-- postorder(NULL) -> return
| +-- postorder(F)
| | +-- postorder(NULL) -> return
| | +-- postorder(NULL) -> return
| | +-- visit(F) -> 输出 "F "
| +-- visit(C) -> 输出 "C "
+-- visit(A) -> 输出 "A " // 根在最后面!
输出: G H D E B F C ANOTE
时间复杂度: O(n)——每个节点恰好被访问一次。空间复杂度: 递归调用栈深度 O(h),h 为树高。最坏情况(树退化为链表,h=n)时递归栈空间 O(n),平衡树时约 O(log n)。
2.3 不同形状树的三序遍历对比
| 树结构 | 前序 | 中序 | 后序 | 特点 |
|---|---|---|---|---|
单节点 A | A | A | A | 三种遍历相同 |
左斜 A->B->C | A B C | C B A | C B A | 前序=插入序,中后序=逆序 |
右斜 A->B->C | A B C | A B C | C B A | 前中序相同,后序逆序 |
满二叉 A(B,C) | A B C | B A C | B C A | 根在三个不同位置 |
关键观察:
前序遍历第一个元素 = 整棵树的根
后序遍历最后一个元素 = 整棵树的根
看上述任何例子,这个规律始终成立!IMPORTANT
root == NULL 是递归的唯一终止条件--它对应树的递归定义中的"空树"。每个遍历函数的第一行必须判空,否则遇到叶子节点的孩子(NULL)时会解引用空指针导致段错误。这是所有树操作函数的基础约定。
3. 前序 + 中序唯一重构二叉树
3.1 为什么前序 + 中序可以?核心直觉
已知:
前序: A B D E C F G <- 第一个元素 A = 根
中序: D B E A F C G <- 在 A 左边的是左子树, 右边的是右子树
步骤 1: 前序首元素 A 是根
在中序中找到 A 的位置:
中序: [D B E] A [F C G]
^左子树 ^右子树
左子树中序: D B E (3个节点)
右子树中序: F C G (3个节点)
步骤 2: 前序中跳过根 A,接下来的 3 个节点是左子树的前序
左子树前序: B D E -> B 是左子树的根
在中序 [D B E] 中找到 B:
[D] B [E] -> B 的左子树: D, B 的右子树: E
步骤 3: 递归构建 D 和 E:
前序 D -> 根
中序 [D] -> 左右皆空 -> D 是叶子
前序 E -> 根
中序 [E] -> 左右皆空 -> E 是叶子
步骤 4: 右子树相同过程:
右子树前序: C F G
右子树中序: F C G
C 是根 -> F 是左子树, G 是右子树
最终还原:
A
/ \
B C
/ \ / \
D E F G3.2 前序 + 后序不能唯一确定
反例: 两棵不同的树可能有相同的前序和后序
树 A: 树 B:
A A
/ \
B B
前序 A B 前序 A B <- 相同!
后序 B A 后序 B A <- 相同!
但树结构不同!
原因: 前序和后序都缺少"根-子树分界"信息
中序之所以关键,是因为它明确标识了"根在哪里分割了左右子树"4. 中序遍历 BST:有序序列的"指纹"
4.1 BST 中序 = 有序--为什么?
BST 示例:
5
/ \
3 7
/ \ \
2 4 8
中序遍历: 2 -> 3 -> 4 -> 5 -> 7 -> 8 <- 从小到大!
原因分析:
+----------------------------------------------------------+
| BST 定义: 左子树所有值 < 根值 < 右子树所有值 |
| |
| 中序遍历: 左子树 -> 根 -> 右子树 |
| |
| 先访问左子树(小值)-> 再访问根(中间值)-> |
| 再访问右子树(大值) |
| |
| 这个顺序天然形成有序序列! |
+----------------------------------------------------------+验证 BST 是否合法的最快方法就是中序遍历--如果输出不是有序的,就一定不是 BST。
这就是为什么 Lesson 38 用中序来验证 BST 操作的正确性。
这个性质是 BST 的"指纹"--中序有序 <=> 这棵树是 BST(必要条件)。TIP
中序有序是 BST 的必要条件,但不是充分条件。一棵中序有序的树可能违反"所有左子树节点 < 根"的全局约束(而不仅仅是直接左孩子 < 根)。不过在大多数入门场景中,中序有序已经是非常强的判断依据。
5. 非递归遍历:显式栈
5.1 为什么需要非递归?
递归遍历依赖函数调用栈,树很深时可能导致栈溢出(stack overflow)。非递归遍历手动维护一个显式栈(数组),用循环模拟递归过程,避免系统调用栈的限制。
5.2 非递归前序遍历
c
#include <stdio.h>
#include <stdlib.h>
#define MAX 256
void preorder_iter(struct node *root) {
if (root == NULL) return;
struct node *stack[MAX];
int top = -1;
stack[++top] = root; // 根入栈
while (top >= 0) {
struct node *cur = stack[top--]; // 弹出栈顶
printf("%c ", cur->ch); // 访问
/* 先右后左入栈--栈是 LIFO,这样出栈时左先出 */
if (cur->right) stack[++top] = cur->right;
if (cur->left) stack[++top] = cur->left;
}
}非递归前序的执行过程(以 A(B,C) 为例):
初始: stack = [A]
-----------------
弹出 A -> 打印 A, 入栈 C 再 B: stack = [B, C]
弹出 B -> 打印 B, B 无孩子: stack = [C]
弹出 C -> 打印 C, C 无孩子: stack = []
栈空 -> 结束
输出: A B C5.3 非递归中序遍历
c
void inorder_iter(struct node *root) {
struct node *stack[MAX];
int top = -1;
struct node *cur = root;
while (cur != NULL || top >= 0) {
/* 一路向左,沿途节点入栈 */
while (cur != NULL) {
stack[++top] = cur;
cur = cur->left;
}
/* 左子树走到底,弹出栈顶(最左节点) */
cur = stack[top--];
printf("%c ", cur->ch); // 访问
/* 转向右子树 */
cur = cur->right;
}
}非递归中序的核心思想:一路向左入栈 -> 退栈访问 -> 转向右子树。这是"左-根-右"在循环中的模拟--先把所有左孩子入栈,退栈时恰好按"左-根-右"的顺序访问。
NOTE
非递归遍历复杂度: 时间复杂度 O(n),每个节点恰好入栈出栈一次。空间复杂度 O(h),显式栈最多同时存储一条从根到叶子的路径上的节点。非递归遍历用显式数组替代了系统调用栈,避免了栈溢出风险但空间复杂度与递归版本相同,也是 O(h)。
6. Morris 遍历:O(1) 空间
6.1 核心思想--利用空闲指针
Morris 遍历的洞察:叶子节点的 left 和 right 都空闲(指向 NULL)。可以利用这些空闲指针建立临时"线索"(thread),避免使用栈。
普通递归/栈: O(h) 额外空间(栈帧 / 数组)
Morris 遍历: O(1) 额外空间(只用了几个指针变量)
代价: 需要在遍历过程中修改树结构(建立临时右指针),遍历完还原6.2 Morris 中序遍历(概念示意)
c
/* Morris 中序遍历--O(1) 空间(概念示意) */
void morris_inorder(struct node *root) {
struct node *cur = root;
while (cur != NULL) {
if (cur->left == NULL) {
/* 没有左子树:访问当前节点,转到右子树 */
printf("%c ", cur->ch);
cur = cur->right;
} else {
/* 找左子树的最右节点(中序前驱) */
struct node *pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
/* 建立线索:pre 的 right 指向 cur */
pre->right = cur;
cur = cur->left; // 去处理左子树
} else {
/* 还原线索:已访问完左子树 */
pre->right = NULL;
printf("%c ", cur->ch);
cur = cur->right; // 去处理右子树
}
}
}
}Morris 遍历的时间复杂度仍然是 O(n)(每个节点最多被访问 4 次),空间复杂度 O(1)。代价: 遍历过程中会暂时修改树的结构(建立临时右指针线索),遍历完成后还原。在不允许递归调用栈的场景(如嵌入式系统、极限内存环境)中具有实际价值。
7. 三种遍历的应用场景
| 遍历 | 应用场景 | 原因 |
|---|---|---|
| 前序 | (1) 序列化/反序列化二叉树 (2) 打印目录结构 (3) 前缀表达式 | 根在最前--重建时先创建根节点,再递归左右 |
| 中序 | (1) BST 有序输出 (2) 中缀表达式 (3) 判断 BST 合法性 | BST 的中序天然有序 |
| 后序 | (1) 删除整棵树(安全释放) (2) 后缀表达式求值 (3) 计算目录大小 | 先处理子节点再处理父节点--不会出现"释放父节点后无法访问子节点"的问题 |
后序释放树的安全设计:
c
/* 后序遍历释放全部节点--安全的方式 */
void free_tree(struct node *root) {
if (root == NULL) return;
free_tree(root->left); // (1) 先释放左子树
free_tree(root->right); // (2) 再释放右子树
free(root); // (3) 最后释放根
}
// 如果用前序释放: free(root) -> free(left) -> X left 已被释放,无法访问!参考解答
练习: 二叉树三种遍历完整实现
c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char ch;
struct node *left, *right;
};
struct node *make_node(char ch) {
struct node *p = malloc(sizeof(*p));
p->ch = ch;
p->left = p->right = NULL;
return p;
}
/* 按层序构建二叉树:token 流,'.' 表示空节点 */
struct node *build_tree(char *tokens) {
if (!tokens || !*tokens) return NULL;
char *tok = strtok(tokens, " \n");
if (!tok || *tok == '.') return NULL;
struct node *root = make_node(*tok), *queue[256];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
struct node *cur = queue[front++];
/* 左孩子 */
tok = strtok(NULL, " \n");
if (tok && *tok != '.') {
cur->left = make_node(*tok);
queue[rear++] = cur->left;
}
/* 右孩子 */
tok = strtok(NULL, " \n");
if (tok && *tok != '.') {
cur->right = make_node(*tok);
queue[rear++] = cur->right;
}
}
return root;
}
/* 前序遍历:根 -> 左 -> 右 */
void preorder(struct node *root) {
if (root == NULL) return;
printf("%c ", root->ch);
preorder(root->left);
preorder(root->right);
}
/* 中序遍历:左 -> 根 -> 右 */
void inorder(struct node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%c ", root->ch);
inorder(root->right);
}
/* 后序遍历:左 -> 右 -> 根 */
void postorder(struct node *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%c ", root->ch);
}
int main(void) {
char line[256];
fgets(line, sizeof(line), stdin);
struct node *root = build_tree(line);
printf("preorder: ");
preorder(root);
printf("\n");
printf("inorder: ");
inorder(root);
printf("\n");
printf("postorder: ");
postorder(root);
printf("\n");
return 0;
}核心逻辑解析:
root == NULL终止:每个遍历函数的第一行判空--空树是递归的基础情况,与树的数学定义同构。- 三种遍历只有
printf位置不同:前序先打印再递归,中序在两次递归之间打印,后序在两次递归之后打印。 build_tree按层序构建:用队列(BFS)读取 token 流,.表示空节点,逐层连接左右孩子。
对照检查:每个函数第一行判了
if (root == NULL) return;吗?前序的printf在两行递归调用的前面吗?中序的printf在两次递归调用之间吗?后序的printf在两次递归调用的后面吗?
课堂讨论
- 三种遍历的代码几乎一模一样--只有一行
printf的位置不同。这个设计体现了什么编程思想? - 前序遍历的第一个元素为什么一定是整棵树的根?后序遍历的最后一个元素为什么也一定是根?
- 如果已知一棵树的前序和中序序列,能不能还原这棵二叉树?如果能,描述你的还原算法;如果不能,给出反例。
- 为什么释放整棵树必须用后序遍历?用前序或中序释放会出什么问题?
- 非递归遍历用显式栈替代递归隐式栈--这背后反映了函数调用栈的什么本质?
讨论答案
Q1: 三种遍历只有 printf 位置不同--体现了什么?
体现了"算法骨架相同,访问时机不同"的编程思想--也叫策略模式(Strategy Pattern)的前身。
c
// 三种遍历的统一骨架:
void traverse(struct node *root, int mode) {
if (root == NULL) return;
if (mode == PRE) printf("%c ", root->ch); // 前序在此
traverse(root->left, mode);
if (mode == IN) printf("%c ", root->ch); // 中序在此
traverse(root->right, mode);
if (mode == POST) printf("%c ", root->ch); // 后序在此
}三种遍历的控制流完全相同(先左后右的递归访问路径),只是在路径上的三个不同位置(进入节点时、左子树返回后、右子树返回后)分别执行访问操作。这种"分离遍历路径与节点处理"的思想在编译器的 AST 遍历、文件系统遍历等场景中广泛应用。
Q2: 前序首元素 = 根,后序末元素 = 根--为什么?
这是前序和后序的定义决定的。
前序定义: 根 -> 左 -> 右
第一个被执行的操作 = 访问根 = 前序的第一个元素
后序定义: 左 -> 右 -> 根
最后一个被执行的操作 = 访问根 = 后序的最后一个元素
只要树非空,这个性质永远成立。
它不需要"看"完整棵树就能判断--只看第一个/最后一个字符就能确认根节点。这个性质在二叉树重建算法中至关重要--重建的第一步就是从前序(或后序)中识别根节点。
Q3: 前序 + 中序能唯一还原二叉树吗?
能。算法递归描述如下:
- 前序的第一个元素是根 r
- 在中序中找到 r 的位置--r 左边是左子树的中序,右边是右子树的中序
- 统计左子树中序的长度 L--前序中跳过 r,接下来的 L 个元素就是左子树的前序
- 前序剩余部分就是右子树的前序
- 递归地对左子树和右子树执行步骤 1-4
前序 + 中序 -> 唯一
后序 + 中序 -> 唯一(后序最后一个元素是根,其余同理)
前序 + 后序 -> 不唯一
反例:
树 A: A 前序: A B 后序: B A
/
B
树 B: A 前序: A B 后序: B A
\
B
两棵树前序和后序都相同,但结构不同!
原因: 缺少中序中"根在中间分割左右子树"的信息。Q4: 为什么释放树必须用后序遍历?
c
// 后序释放--正确
void free_post(struct node *root) {
if (root == NULL) return;
free_post(root->left); // 先释放左子树
free_post(root->right); // 再释放右子树
free(root); // 最后释放根
}
// 前序释放--需先保存孩子指针才能工作
void free_pre(struct node *root) {
if (root == NULL) return;
struct node *l = root->left; // 先保存孩子指针
struct node *r = root->right;
free(root); // 释放根
free_pre(l); // 然后释放孩子?已保存指针所以能工作
free_pre(r);
}
// 中序释放--最危险
void free_in(struct node *root) {
if (root == NULL) return;
free_in(root->left);
free(root); // 释放根
free_in(root->right); // root->right 已被释放!野指针!
}后序释放最安全、最自然--它保证每个节点的子节点在父节点被释放前已经处理完毕。这与"从叶子向根逐层释放"的直觉一致。
Q5: 非递归遍历用显式栈--反映了调用栈的什么本质?
调用栈本质上就是一种"后进先出"的数据结构--每次函数调用入栈帧,返回时出栈帧。
递归版本:
preorder(A) -> 调用 preorder(B) -> 调用 preorder(D) -> return -> ...
| | |
调用栈: [preorder(A)] [preorder(A), preorder(B)]
[preorder(A), preorder(B), preorder(D)]
非递归版本:
stack = [A] -> 弹出 A, 入栈 C, B -> 弹出 B -> 弹出 C
函数调用栈的三个要素:
(1) 保存返回地址(回到谁调用我的那一行)
(2) 保存局部变量(每个递归层的上下文)
(3) LIFO 顺序(最后调用的最先返回)
非递归显式栈模拟的是这三个要素--只不过"返回地址"变成了循环位置,
"局部变量"已经编码在节点指针中(通过 left/right),"LIFO"由数组模拟。理解了这个等价关系,就可以在任何需要深度优先搜索的场景中自由切换递归和非递归写法。
课后练习
统计树的高度 编写
int tree_height(struct node *root)函数,返回二叉树的高度(空树高度为 0)。提示:树高 = 1 + max(左子树高, 右子树高)。知识点提示:递归定义--空树高为 0,非空树高为 1 + 左右子树中较高者。与遍历的递归结构同构:处理根 + 递归左右。
参考解答
cint tree_height(struct node *root) { if (root == NULL) return 0; int lh = tree_height(root->left); int rh = tree_height(root->right); return 1 + (lh > rh ? lh : rh); }与遍历函数的结构完全一致:判空 -> 递归左右 -> 处理根(取 max + 1)。这是树的递归定义在"计算属性"场景下的直接应用。
统计节点总数。编写
int count_nodes(struct node *root)函数,返回二叉树的节点总数。提示:节点数 = 1 + 左子树节点数 + 右子树节点数。知识点提示:与前序遍历的访问顺序一致(先计数根节点,再递归左右)。空树返回 0。
参考解答
cint count_nodes(struct node *root) { if (root == NULL) return 0; return 1 + count_nodes(root->left) + count_nodes(root->right); }每个节点的贡献为 1,累加左右子树--这是递归设计的"分治"思想:把整棵树的问题分解为左子树 + 右子树 + 当前节点。
判断两棵树是否相同。编写
int is_same(struct node *a, struct node *b)函数,判断两棵二叉树的结构和值是否完全相同。知识点提示:同时递归遍历两棵树,每一步比较当前节点的值和左右子树。空树与空树相同,空树与非空树不同。
参考解答
cint is_same(struct node *a, struct node *b) { if (a == NULL && b == NULL) return 1; // 都空 -> 相同 if (a == NULL || b == NULL) return 0; // 一空一非空 -> 不同 if (a->ch != b->ch) return 0; // 值不同 -> 不同 return is_same(a->left, b->left) && // 左子树相同? is_same(a->right, b->right); // 右子树也相同? }这是前序遍历的变体--先比较根,再递归比较左右子树。递归的终止条件从一种变成了四种(都空、a 空、b 空、值不同),但结构骨架不变。
非递归后序遍历。后序遍历的非递归实现比前序和中序更复杂--需要两次访问节点(第一次越过,第二次打印)。编写
void postorder_iterative(struct node *root)。知识点提示:需要用
prev指针标记上次访问的节点。关键挑战:在第二次访问节点时才打印(先处理完左右子树才能处理根)。参考解答
cvoid postorder_iter(struct node *root) { if (root == NULL) return; struct node *stack[256], *cur = root, *last = NULL; int top = -1; while (cur || top >= 0) { /* 一路向左入栈 */ while (cur) { stack[++top] = cur; cur = cur->left; } cur = stack[top]; /* 右子树未访问 -> 转右;否则访问根 */ if (cur->right && cur->right != last) { cur = cur->right; } else { printf("%c ", cur->ch); last = cur; top--; cur = NULL; } } }后序非递归的难点在于"第二次经过节点"才访问--需要
last指针记录上次访问的节点,判断右子树是否已经处理完毕。
参考资料
- 《算法导论》第 12 章 二叉搜索树(遍历部分)--递归遍历的严格数学描述
- 《数据结构与算法分析 - C 语言描述》§4.1-4.2 --树的基本概念与遍历实现
- Morris Traversal - GeeksforGeeks -- O(1) 空间的 Morris 遍历详解
- Binary Tree Traversals - VisuAlgo -- 交互式可视化的树遍历动画演示
- 《The C Programming Language (K&R)》§6.5 -- 自引用结构与递归(
struct node的设计模式)
"Recursion is the root of computation since it trades description for time." -- Alan J. Perlis