408 高频考点精讲:二叉树的遍历(Binary Tree Traversals)¶
模块归属:数据结构 · 树与二叉树
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:4 次(2016~2025 年:2017#4、2017#5、2020#4、2024#3)
- 历年总考查频次:7 次(含 2011#5、2014#4、2015#5)
- 出题形式:单项选择题(分值 2 分)为主,常作为算法综合设计大题的底层遍历与剪枝基础
- 命题特点:
- 局部拓扑及孩子存在性判定:突破传统遍历序列模拟,深入考查中序前驱后继结点的结构极端性(如 2024#3 考查度为 2 结点在中序序列中相邻元素的孩子指针状态)。
- 跨数据结构遍历映射:将通用树、森林的遍历及“左孩子右兄弟”二叉树遍历深度绑定(如 2020#4 考查森林先根、中根序列向二叉树后序序列的推演)。
- 遍历序列代数等价性:考查先序、中序、后序遍历序列重合时,二叉树拓扑结构所必须满足的充要条件(如 2017#4)。
- 给定树形拓扑的反向标定:结合二叉树的对称性或局部结构,依据后序序列反推结点所属层级及相对位置关系(如 2017#5)。
二、 具体考察内容¶
1. 二叉树遍历的形式化定义及递归数学模型¶
二叉树遍历(Binary Tree Traversal)是指按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次且仅被访问一次。遍历操作的本质是将非线性的树状层次结构转化为线性序列。
设非空二叉树为 \(T\)$ \text{,根结点记为} $\(r = \text{root}(T)\)$ \text{,其左子树记为} $\(T_L\)$ \text{,右子树记为} $\(T_R\)$ \text{。记序列串联操作符为} $\(\circ\)$ \text{,空序列为} $\(\varepsilon\)。三种核心深度优先遍历的形式化递归定义如下:
(1) 先序遍历(Preorder Traversal, NLR)¶
- 递归定义:若二叉树为空,则执行空操作;否则:
- 访问根结点 \(r\);
- 先序遍历左子树 \(T_L\);
- 先序遍历右子树 \(T_R\)。
- 数学形式化表达式: $\(\text{Preorder}(T) = \begin{cases} \varepsilon, & T = \emptyset \\ \langle r \rangle \circ \text{Preorder}(T_L) \circ \text{Preorder}(T_R), & T \neq \emptyset \end{cases}\)$
(2) 中序遍历(Inorder Traversal, LNR)¶
- 递归定义:若二叉树为空,则执行空操作;否则:
- 中序遍历左子树 \(T_L\);
- 访问根结点 \(r\);
- 中序遍历右子树 \(T_R\)。
- 数学形式化表达式: $\(\text{Inorder}(T) = \begin{cases} \varepsilon, & T = \emptyset \\ \text{Inorder}(T_L) \circ \langle r \rangle \circ \text{Inorder}(T_R), & T \neq \emptyset \end{cases}\)$
(3) 后序遍历(Postorder Traversal, LRN)¶
- 递归定义:若二叉树为空,则执行空操作;否则:
- 后序遍历左子树 \(T_L\);
- 后序遍历右子树 \(T_R\);
- 访问根结点 \(r\)。
- 数学形式化表达式: $\(\text{Postorder}(T) = \begin{cases} \varepsilon, & T = \emptyset \\ \text{Postorder}(T_L) \circ \text{Postorder}(T_R) \circ \langle r \rangle, & T \neq \emptyset \end{cases}\)$
(4) 层序遍历(Level-order Traversal)¶
- 广度优先访问机理:从树的根结点出发,自顶向下按层访问(第 1 层至第 \(h\) 层),在同层结点中自左向右依次访问。
- 数学特征:若结点 \(u\)$ \text{的深度小于结点} $\(v\)$ \text{的深度,则} $\(u\)$ \text{必在} $\(v\)$ \text{之前被访问;若深度相同且} $\(u\)$ \text{位于} $\(v\)$ \text{的左侧,则} $\(u\)$ \text{先于} $\(v\) 被访问。
2. 遍历算法的非递归实现机理及栈状态演化¶
在计算机底层执行环境中,递归调用依赖系统调用栈保存现场信息。非递归遍历算法通过显式引入辅助栈(Stack)或辅助队列(Queue)来模拟程序运行状态。
(1) 中序遍历非递归栈实现(LNR)¶
- 执行逻辑:
- 沿当前结点的左分支一路向左下深入,将沿途遇到的所有结点逐一压入栈中,直至当前指针为空;
- 弹出栈顶结点并执行访问操作;
- 将当前指针转向已访问结点的右孩子,重复步骤 1,直至栈空且当前指针为空。
void InOrderNonRecursive(BiTree T) {
InitStack(S);
BiTree p = T;
while (p != NULL || !IsEmpty(S)) {
if (p != NULL) {
Push(S, p);
p = p->lchild; // 一路向左深入
} else {
Pop(S, p);
visit(p); // 弹出并访问
p = p->rchild; // 转向右子树
}
}
}
- 状态分析:每个结点进栈一次、出栈一次。访问发生在结点自栈顶弹出、且其左子树已完全遍历完毕的时刻。
(2) 先序遍历非递归栈实现(NLR)¶
- 实现路径:只需将中序遍历代码中的访问时机前移至进栈之前(即遇到结点即刻访问,随后压栈并深入左子树);或者采用“根出栈,右孩子先入栈、左孩子后入栈”的简化逻辑。
void PreOrderNonRecursive(BiTree T) {
if (T == NULL) return;
InitStack(S);
Push(S, T);
while (!IsEmpty(S)) {
BiTree p;
Pop(S, p);
visit(p);
if (p->rchild != NULL) Push(S, p->rchild); // 右孩子先入后出
if (p->lchild != NULL) Push(S, p->lchild); // 左孩子后入先出
}
}
(3) 后序遍历非递归栈实现(LRN,核心难点)¶
后序遍历要求左、右子树均访问完毕后方可访问根结点。当指针从左子树返回时,不能弹出根结点;只有当指针从右子树返回时,才能执行弹出与访问。
- 单栈辅助变量法(
lastVisited标志): - 栈中保留从根到当前结点的所有祖先路径;
- 仅当当前结点的右子树为空,或者其右孩子刚刚被访问过(
p->rchild == r)时,说明左右子树已遍历完毕,方可出栈并访问。
void PostOrderNonRecursive(BiTree T) {
InitStack(S);
BiTree p = T;
BiTree r = NULL; // 记录最近访问过的结点
while (p != NULL || !IsEmpty(S)) {
if (p != NULL) {
Push(S, p);
p = p->lchild; // 一路向左深入
} else {
GetTop(S, p); // 查看栈顶,暂不出栈
if (p->rchild != NULL && p->rchild != r) {
p = p->rchild; // 转向右子树深入
} else {
Pop(S, p); // 左右均已处理,出栈访问
visit(p);
r = p; // 更新最近访问记录
p = NULL; // 保证下一轮继续弹栈检查
}
}
}
}
- 双栈逆向法:由于后序遍历顺序为
[左, 右, 根],其逆序为[根, 右, 左]。可按类似先序的方式遍历出[根, 右, 左]并依次压入辅助栈 \(S_2\)$ \text{,最终自} $\(S_2\) 顺序弹出,即得后序序列。
(4) 层序遍历的辅助队列实现¶
- 算法框架:根结点入队;当队列非空时,队头出队并访问,若其左孩子存在则入队,若其右孩子存在则入队。此过程严格遵循 BFS 拓扑序。
3. 中序遍历局部相邻性定理及孩子存在性判定¶
在 408 考研命题中,利用遍历定义的单调性分析结点指针的存在性属于极高频题型(如 2024#3)。
(1) 中序前驱定理(Inorder Predecessor Theorem)¶
- 定理陈述:设二叉树中结点 \(v\)$ \text{拥有左孩子(即} $\(T_L \neq \emptyset\)$ \text{),则结点} $\(v\)$ \text{在中序遍历序列中的直接前驱结点} $\(p\)$ \text{必为左子树} $\(T_L\)$ \text{中的最右下结点(即从左孩子} $\(v \to \text{lchild}\) 开始沿
rchild指针不断下行直至右指针为空的结点)。 - 推论(前驱孩子性质):结点 \(p\)$ \text{必然没有右孩子(} $\(p \to \text{rchild} = \text{NULL}\))。
- 证明(反证法):
- 假设 \(p\)$ \text{拥有右孩子} $\(w\)。
- 根据中序遍历定义 \(\text{Inorder}(T_p) = \langle \text{Inorder}(T_{pL}), p, \text{Inorder}(T_{pR}) \rangle\)。
- 由于 \(w \in T_{pR}\)$ \text{,则结点} $\(w\)$ \text{的中序访问时机必然滞后于结点} $\(p\)。
- 又因 \(p\)$ \text{属于} $\(v\)$ \text{的左子树,整个} $\(T_L\)$ \text{的访问时机均先于根} $\(v\)。
- 故在全局中序遍历序列中,访问顺序必为:\(\cdots, p, \cdots, w, \cdots, v, \cdots\)。
- 这意味着在 \(p\)$ \text{与} $\(v\)$ \text{之间必然存在至少一个结点} $\(w\)$ \text{,与“} $\(p\)$ \text{是} $\(v\) 的直接前驱(在中序序列中相邻)”的假设发生绝对矛盾。
- 因此假设不成立,\(p\) 绝不可能有右孩子。
(2) 中序后继定理(Inorder Successor Theorem)¶
- 定理陈述:设二叉树中结点 \(v\)$ \text{拥有右孩子(即} $\(T_R \neq \emptyset\)$ \text{),则结点} $\(v\)$ \text{在中序遍历序列中的直接后继结点} $\(q\)$ \text{必为右子树} $\(T_R\)$ \text{中的最左下结点(即从右孩子} $\(v \to \text{rchild}\) 开始沿
lchild指针不断下行直至左指针为空的结点)。 - 推论(后继孩子性质):结点 \(q\)$ \text{必然没有左孩子(} $\(q \to \text{lchild} = \text{NULL}\))。
- 证明(反证法):
- 假设 \(q\)$ \text{拥有左孩子} $\(u\)。
- 根据中序遍历定义,结点 \(u\)$ \text{属于} $\(q\)$ \text{的左子树,其访问时机必然先于} $\(q\)。
- 又因 \(q\)$ \text{属于} $\(v\)$ \text{的右子树,整个} $\(T_R\)$ \text{的访问时机均滞后于根} $\(v\)。
- 故在全局中序遍历序列中,访问顺序必为:\(\cdots, v, \cdots, u, \cdots, q, \cdots\)。
- 这表明在 \(v\)$ \text{与} $\(q\)$ \text{之间必然插入了结点} $\(u\)$ \text{,与“} $\(q\)$ \text{是} $\(v\) 的直接后继(在中序序列中紧密相邻)”发生矛盾。
- 因此假设不成立,\(q\) 绝不可能有左孩子。
(3) 双孩子结点的极端结构推论¶
- 综合推论:若二叉树中度为 2 的结点 \(v\)$ \text{的中序遍历紧邻邻居为} $\(\langle \cdots, p, v, q, \cdots \rangle\),则必满足: $$ \text{\begin{cases} p \text{ 必定无右孩子} & (p} \to \text{rchild} = \text{NULL}) \ q \text{ 必定无左孩子} & (q \to \text{lchild} = \text{NULL}) \end{cases} $$ 注:\(p\)$ \text{可以有左孩子(作为其自身子树),} $\(q\)$ \text{可以有右孩子,但绝对无法拥有面向} $\(v\) 方向的孩子指针。
4. 遍历序列唯一确定二叉树的代数定理¶
(1) 基本判定定理¶
- 充要条件定理:给定一棵二叉树的中序遍历序列,再加上先序遍历序列、后序遍历序列或层序遍历序列中的任意一种,且各结点关键字互不相同,则可唯一确定该二叉树的拓扑结构与结点内容。
- 递归划分原理:
- 根结点的确定:先序序列的首元素、后序序列的末元素、层序序列的首元素必然对应当前子树的根结点 \(r\)。
- 左右子树的分割:在中序序列中检索到根结点 \(r\)$ \text{,其左侧所有元素构成左子树中序序列} $\(L_{\text{in}}\)$ \text{,右侧所有元素构成右子树中序序列} $\(R_{\text{in}}\)。
- 递归推进:根据 \(L_{\text{in}}\)$ \text{的长度} $\(|L_{\text{in}}|\),从先序/后序序列中切分出对应长度的左右子树子序列,递归调用构造算法。
(2) “先序 + 后序”无法唯一确定树形的本质推导¶
- 歧义性根源:中序序列的作用在于区分“左”和“右”。在先序序列中,子树形态为 $$ \text{\langle \text{根}, \text{左子树}, \text{右子树} \rangle} $$;在后序序列中,子树形态为 $$ \text{\langle \text{左子树}, \text{右子树}, \text{根} \rangle} $$。
- 单分支结点的不可辨识性:
- 考虑单分支子树:设根为 \(A\)$ \text{,唯一的子结点为} $\(B\)。
- 若 \(B\)$ \text{为左孩子,则先序为} $\(\langle A, B \rangle\)$ \text{,后序为} $\(\langle B, A \rangle\)。
- 若 \(B\)$ \text{为右孩子,则先序仍为} $\(\langle A, B \rangle\)$ \text{,后序亦为} $\(\langle B, A \rangle\)。
- 两种完全不同的二叉树拓扑,产生完全相同的先序与后序序列。
- 定量计算定理:若一棵二叉树中已知先序序列和后序序列,且该二叉树中度为 1 的结点总数为 \(n_1\),则满足该先序和后序序列的不同二叉树形态总数共有: $\(N = 2^{n_1}\)$
- 无歧义特例:若明确限定二叉树中不存在度为 1 的结点(即所有非叶结点的度均为 2,称为严格二叉树/满二叉树),则先序序列与后序序列能够唯一确定该二叉树的拓扑结构。
5. 特定遍历序列重合的充要条件¶
考研中常以选择题形式考查不同遍历序列完全相同或呈逆序时二叉树必须满足的形态。
| 遍历序列关系 | 充要条件 | 拓扑形态特征 |
|---|---|---|
| 先序序列 = 中序序列 | 所有非叶结点只有右子树(无左子树) | 任意结点的左孩子指针均为 NULL(右斜链或空树) |
| 中序序列 = 后序序列 | 所有非叶结点只有左子树(无右子树) | 任意结点的右孩子指针均为 NULL(左斜链或空树) |
| 先序序列 = 后序序列 | 树为空树,或仅含单个根结点 | 节点总数 \(n \le 1\) |
| 先序序列 = 后序序列的逆序 | 树中任意结点的度数 \(\le 1\) | 任意非叶结点仅有单支(退化为链状形态) |
(1) “先序 = 中序”的数学证明¶
- 由定义:\(\text{Preorder}(T) = \langle r \rangle \circ \text{Preorder}(T_L) \circ \text{Preorder}(T_R)\);\(\text{Inorder}(T) = \text{Inorder}(T_L) \circ \langle r \rangle \circ \text{Inorder}(T_R)\)。
- 若两序列相等,首元素必须相同。
- 先序首元素为 \(r\)$ \text{。中序首元素若存在左子树} $\(T_L \neq \emptyset\)$ \text{,则中序首元素为} $\(T_L\)$ \text{中最左下结点,必与} $\(r\) 不等。
- 欲使首元素恒为 \(r\)$ \text{,必须有} $\(T_L = \emptyset\)。
- 对右子树 \(T_R\) 递归应用此规则,可知二叉树中每个非叶结点的左子树均必须为空,即所有非叶结点只有右子树。
(2) “先序 = 后序逆序”的数学证明¶
- 先序:\(\langle r \rangle \circ \text{Preorder}(T_L) \circ \text{Preorder}(T_R)\)。
- 后序的逆序:\(\text{Reverse}(\text{Postorder}(T)) = \langle r \rangle \circ \text{Reverse}(\text{Postorder}(T_R)) \circ \text{Reverse}(\text{Postorder}(T_L))\)。
- 要使二者对于子序列长度与元素完全匹配,左右子树必有一方为空。即对于树中任意非叶结点,不能同时存在左孩子与右孩子(度不能为 2,结点的度只能为 0 或 1)。
6. 树、森林与二叉树遍历的映射对应法则¶
在“左孩子右兄弟”(Left-Child Right-Sibling, LCRS)表示法下,树、森林与二叉树之间存在确定的一一映射关系。
(1) 映射等价表¶
| 森林遍历方式 | 二叉树遍历方式 | 遍历次序与处理逻辑 |
|---|---|---|
| 森林的先根遍历 | 对应二叉树的先序遍历 | 先访问第一棵树的根,再先根遍历第一棵树中根结点的子树森林,最后先根遍历其余树组成的森林 |
| 森林的后根遍历(中根遍历) | 对应二叉树的中序遍历 | 先后根遍历第一棵树中根结点的子树森林,再访问第一棵树的根,最后后根遍历其余树组成的森林 |
关键命题陷阱: 1. 树的后根遍历对应的是二叉树的中序遍历,而不是二叉树的后序遍历。 2. 森林的后根遍历在部分教材中亦被称为中根遍历。 3. 若题目给出森林的先根与中根遍历序列,求对应二叉树的后序遍历,本质考查:已知先序序列与中序序列还原二叉树,并求该二叉树的后序遍历。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 3 题 · 中序局部相邻性及孩子指针状态判定¶
题目
\(p\)、\(q\)、\(v\)$ \text{都是二叉树} $\(T\)$ \text{中的结点,二叉树} $\(T\)$ \text{的中序遍历为} $\(\cdots, p, v, q, \cdots\)$ \text{,其中} $\(v\) 有两个孩子结点,则下列说法正确的是( )。
A. \(p\)$ \text{没右孩子,} $\(q\) 没左孩子
B. \(p\)$ \text{没右孩子,} $\(q\) 有左孩子
C. \(p\)$ \text{有右孩子,} $\(q\) 没左孩子
D. \(p\)$ \text{有右孩子,} $\(q\) 有左孩子
【解析】¶
- 中序遍历拓扑定位: 中序遍历次序为“左子树 \(\to\)$ \text{根结点} $\(\to\) 右子树”。 题目给出结点 \(v\)$ \text{具有两个孩子结点,说明} $\(v\)$ \text{的左子树} $\(T_L\)$ \text{与右子树} $\(T_R\) 均非空。
- 分析结点 \(p\)(\(v\) 的中序直接前驱):
- 既然 \(v\)$ \text{存在左子树} $\(T_L\)$ \text{,根据中序遍历定义,} $\(v\)$ \text{之前被访问的最后一个结点必在} $\(T_L\)$ \text{中,即} $\(p \in T_L\)。
- 具体而言,\(p\)$ \text{是} $\(T_L\)$ \text{中中序最后被访问的结点,即} $\(T_L\) 的“最右下结点”。
- 假设 \(p\)$ \text{拥有右孩子} $\(p_{\text{right}}\)$ \text{,根据中序遍历次序,} $\(p_{\text{right}}\)$ \text{的访问时序必然落在} $\(p\)$ \text{之后、但在根} $\(v\)$ \text{之前。如此一来,全局序列中} $\(p\)$ \text{与} $\(v\)$ \text{之间必然被} $\(p_{\text{right}}\)$ \text{隔开,与题设“} $\(p\)$ \text{与} $\(v\) 在中序序列中相邻”矛盾。
- 因此,\(p\) 绝不能有右孩子。
- 分析结点 \(q\)(\(v\) 的中序直接后继):
- 既然 \(v\)$ \text{存在右子树} $\(T_R\)$ \text{,根据中序遍历定义,} $\(v\)$ \text{之后被访问的首个结点必在} $\(T_R\)$ \text{中,即} $\(q \in T_R\)。
- 具体而言,\(q\)$ \text{是} $\(T_R\)$ \text{中中序最先被访问的结点,即} $\(T_R\) 的“最左下结点”。
- 假设 \(q\)$ \text{拥有左孩子} $\(q_{\text{left}}\)$ \text{,根据中序遍历次序,} $\(q_{\text{left}}\)$ \text{的访问时序必然在根} $\(v\)$ \text{之后、且在} $\(q\)$ \text{之前。如此一来,} $\(v\)$ \text{与} $\(q\)$ \text{之间必然被} $\(q_{\text{left}}\)$ \text{隔开,与题设“} $\(v\)$ \text{与} $\(q\) 在中序序列中相邻”矛盾。
- 因此,\(q\) 绝不能有左孩子。
- 选项辨析:
- A 项:\(p\)$ \text{没右孩子,} $\(q\) 没左孩子,符合定理推论,正确;
- B、C、D 项结论均与推论违背,错误。
正确答案:A
【真题 2】2020 年 408 第 4 题 · 森林及二叉树遍历跨结构推演¶
题目
已知森林 \(F\)$ \text{及与之对应的二叉树} $\(T\)$ \text{,若} $\(F\)$ \text{的先根遍历序列是 a, b, c, d, e, f,中根遍历序列是 b, a, d, f, e, c,则} $\(T\) 的后序遍历序列是( )。
A. b, a, d, f, e, c B. b, d, f, e, c, a
C. b, f, e, d, c, a D. f, e, d, c, b, a
【解析】¶
- 遍历映射关系转化: 根据森林与二叉树转换的 LCRS 法则:
- 森林 \(F\)$ \text{的先根遍历序列} $\(\equiv\)$ \text{对应二叉树} $\(T\)$ \text{的先序遍历序列:} $\(\langle \text{a, b, c, d, e, f} \rangle\);
- 森林 \(F\)$ \text{的中根(后根)遍历序列} $\(\equiv\)$ \text{对应二叉树} $\(T\)$ \text{的中序遍历序列:} $\(\langle \text{b, a, d, f, e, c} \rangle\)。
- 题目转化为:已知二叉树 \(T\) 的先序序列与中序序列,求解其后序遍历序列。
- 递归重构二叉树 \(T\):
- 确定根结点与左右子树划分:
- 先序首元素为 a,故树的根为 a。
- 在中序序列中找到 a:左侧为 \(\langle \text{b} \rangle\)$ \text{,右侧为} $\(\langle \text{d, f, e, c} \rangle\)。
- 得出:根 a 的左子树仅含结点 b;右子树包含集合 \(\{\text{c, d, e, f}\}\)。
- 重构右子树:
- 对应先序子序列为 \(\langle \text{c, d, e, f} \rangle\),首元素为 c,故 a 的右孩子为 c。
- 对应中序子序列为 \(\langle \text{d, f, e, c} \rangle\)$ \text{。结点 c 位于最末尾,说明其右侧无元素,即 c 没有右孩子,集合} $\(\{\text{d, e, f}\}\) 全属于 c 的左子树。
- 重构 c 的左子树:
- 对应先序子序列为 \(\langle \text{d, e, f} \rangle\),根为 d。
- 对应中序子序列为 \(\langle \text{d, f, e} \rangle\)$ \text{。结点 d 位于最前端,说明 d 没有左孩子,集合} $\(\{\text{e, f}\}\) 全属于 d 的右子树。
- 重构 d 的右子树:
- 对应先序子序列为 \(\langle \text{e, f} \rangle\),根为 e。
- 对应中序子序列为 \(\langle \text{f, e} \rangle\)。结点 e 的左侧为 f,说明 f 是 e 的左孩子。
- 还原所得二叉树 \(T\) 的拓扑图:
- 求二叉树 \(T\)$ \text{的后序遍历序列(左} $\(\to\)$ \text{右} $\(\to\) 根):
- 左子树后序:b
- 右子树中:
- 以 e 为根的子树后序:f \(\to\) e
- 以 d 为根的子树后序:(无左) \(\to\) (f, e) \(\to\) d
- 以 c 为根的子树后序:(f, e, d) \(\to\)$ \text{(无右)} $\(\to\) c
- 右子树整体后序为:f, e, d, c
- 全树后序遍历为:\(\langle \text{b, f, e, d, c, a} \rangle\)。
正确答案:C
【真题 3】2017 年 408 第 4 题 · 遍历序列重合充要条件分析¶
题目
要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶节点须满足的条件是( )。
A. 只有左子树 B. 只有右子树
C. 结点的度均为 1 D. 结点的度均为 2
【解析】¶
- 利用递归定义展开代数式: 设二叉树为 \(T\)$ \text{,根为} $\(r\)$ \text{,左、右子树分别为} $\(T_L\)$ \text{与} $\(T_R\)。
- 先序序列:\(\text{Preorder}(T) = \langle r \rangle \circ \text{Preorder}(T_L) \circ \text{Preorder}(T_R)\)
- 中序序列:\(\text{Inorder}(T) = \text{Inorder}(T_L) \circ \langle r \rangle \circ \text{Inorder}(T_R)\)
- 比较首元素与递归约束:
- 若二叉树非空且两序列完全相同,则序列的第一个元素必须相等。
- 先序序列的首元素为根结点 \(r\)。
- 中序序列首先遍历左子树 \(T_L\)$ \text{。若} $\(T_L \neq \emptyset\)$ \text{,则中序序列的首元素是} $\(T_L\)$ \text{中的某个结点(最左下结点),它必然与根结点} $\(r\) 互为不同结点。
- 因此,要使首元素相等,必须强制要求 \(T_L = \emptyset\)(左子树为空)。
- 递归传递性: 若左子树为空,则:
- \(\text{Preorder}(T) = \langle r \rangle \circ \text{Preorder}(T_R)\)
- \(\text{Inorder}(T) = \langle r \rangle \circ \text{Inorder}(T_R)\) 消去根结点 \(r\)$ \text{,要求} $\(\text{Preorder}(T_R) = \text{Inorder}(T_R)\)。 将上述逻辑对右子树 \(T_R\) 及其所有子孙子树递归应用,可得:树中任意一个非叶结点均不能有左子树,即所有非叶结点必须只有右子树。
- 选项逐项辨析:
- A 项:若只有左子树,先序为 \(\langle r, \cdots \rangle\)$ \text{,中序为} $\(\langle \cdots, r \rangle\),两序列完全相反,错误;
- B 项:所有非叶结点只有右子树,符合推导,正确;
- C 项:若结点的度为 1 但为左孩子,先序与中序不相同,故“度为 1”不充分,错误;
- D 项:度为 2 的结点同时拥有左、右子树,先序首元素为根,中序首元素在左子树,二者必然不相等,错误。
正确答案:B
【真题 4】2017 年 408 第 5 题 · 依据树形拓扑及后序序列层级反推¶
题目
已知一棵二叉树的树形如下图所示,其后序序列为 e, a, c, b, d, g, f。树中与结点 a 同层的结点是( )。
A. c B. d C. f D. g
【解析】¶
- 分析树形拓扑结构与分层: 根据原题给出的二叉树结构图,全树呈现高度对称的两大分支体系:
- 第 1 层(深度 1):根结点 (1);
- 第 2 层(深度 2):结点 (2) 为左孩子,结点 (3) 为右孩子;
- 第 3 层(深度 3):结点 (4) 为结点 (2) 的左孩子,结点 (5) 为结点 (3) 的右孩子;
- 第 4 层(深度 4):结点 (6) 为结点 (4) 的右孩子,结点 (7) 为结点 (5) 的左孩子。
- 结合后序遍历规则(左 \(\to\)$ \text{右} $\(\to\) 根)逐一标注结点:
后序遍历序列为:
e, a, c, b, d, g, f,总计 7 个结点。 - 全树根结点:后序序列最后一个元素必为根,故根结点 \((1) = \mathbf{f}\)。
- 左右子树划分:
- 左子树由拓扑编号 2, 4, 6 组成,共 3 个结点;右子树由拓扑编号 3, 5, 7 组成,共 3 个结点。
- 因此后序序列的前 3 个元素
e, a, c属于左子树,中间 3 个元素b, d, g属于右子树。
- 左子树内部标定(后序为
e, a, c):- 左子树的根是其后序最后一个元素,即结点 \((2) = \mathbf{c}\)。
- 结点 (2) 仅有左孩子 (4),因此结点 (4) 及其右孩子 (6) 构成其子树,后序为
e, a。 - 故结点 \((4) = \mathbf{a}\)$ \text{,结点} $\((6) = \mathbf{e}\)。
- 右子树内部标定(后序为
b, d, g):- 右子树的根是其后序最后一个元素,即结点 \((3) = \mathbf{g}\)。
- 结点 (3) 仅有右孩子 (5),后序为
b, d。 - 故结点 \((5) = \mathbf{d}\)$ \text{,结点} $\((7) = \mathbf{b}\)。
- 完成结点拓扑映射并查找同层结点:
text f (第 1 层) / \ (第 2 层) c g / \ (第 3 层) a d \ / (第 4 层) e b - 位于第 1 层的结点为:f;
- 位于第 2 层的结点为:c, g;
- 位于第 3 层的结点为:a, d;
- 位于第 4 层的结点为:e, b。 因此,与结点 a 处于同一层(第 3 层)的结点是 d。
正确答案:B
四、 核心解题套路与易错陷阱¶
1. 中序前驱后继极值判定法(秒杀局部孩子存在性)¶
在解决类似 2024#3 的选择题时,无需画出具体复杂树形,直接运用“极值路径法则”: * 求 \(v\)$ \text{的中序前驱} $\(p\)$ \text{:若} $\(v\)$ \text{有左孩子,则从} $\(v \to \text{lchild}\)$ \text{出发,一路向右走到底。终点} $\(p\)$ \text{必无右孩子(若有右孩子,则该右孩子在中序中介于} $\(p\)$ \text{与} $\(v\) 之间,矛盾)。 * 求 \(v\)$ \text{的中序后继} $\(q\)$ \text{:若} $\(v\)$ \text{有右孩子,则从} $\(v \to \text{rchild}\)$ \text{出发,一路向左走到底。终点} $\(q\)$ \text{必无左孩子(若有左孩子,则该左孩子在中序中介于} $\(v\)$ \text{与} $\(q\) 之间,矛盾)。 * 口诀:“左子树里找最右(无右孩子),右子树里找最左(无左孩子)”。
2. 双遍历序列重构二叉树的三步切割模板¶
当已知前序/后序与中序重构二叉树时,严格执行以下标准化操作: 1. 定根:在前序序列提取首元素(或后序末元素)作为根。 2. 切中序:在中序序列中找到根元素,其中序左半部为左子树所有结点,右半部为右子树所有结点,记左子树长度为 \(k\)。 3. 分前序/后序:在前序序列中,紧随根之后的 \(k\) 个元素必为左子树前序序列,剩余元素为右子树前序序列;递归此过程。
3. 森林与二叉树映射的转化模型¶
面对树与森林遍历题型,牢记转化等价公理: $$ \text{森林先根遍历} \Longleftrightarrow \text{二叉树先序遍历} $$ $$ \text{森林后根遍历(中根遍历)} \Longleftrightarrow \text{二叉树中序遍历} $$ 若题目询问对应二叉树的后序序列,解法固定为两步: 1. 以先根序列为二叉树先序、中根序列为二叉树中序,还原该二叉树; 2. 直接对还原后的二叉树写出后序遍历序列。
4. 高频易错陷阱防范¶
- 陷阱 1:混淆树的后根遍历与二叉树后序遍历
树在转换为二叉树后,原树中根结点的子树均转为其左孩子的右斜链。因此访问完子树再访问根结点的次序,映射在二叉树中恰好是“左子树 \(\to\)$ \text{根} $\(\to\) 右子树”,即中序遍历,切不可望文生义选成后序遍历。 - 陷阱 2:先序与后序能否确定二叉树的判定条件
只有度为 1 的结点才会在“先序 + 后序”确定树形时引入分支方向歧义(左单支或右单支)。若题目明确注明二叉树中每个非叶结点的度数均为 2,则先序和后序能够唯一确定该二叉树的拓扑结构。 - 陷阱 3:单栈非递归后序遍历死循环
在非递归后序遍历中,自右子树返回根结点时,必须借助lastVisited指针判断右孩子是否刚刚被处理过。若漏掉此判定条件,会导致指针重新进入右子树,造成无限循环压栈。
五、 考点速记清单¶
- 三序遍历的核心递归结构:
- 先序(NLR):$$ \text{\langle \text{根}, \text{左}, \text{右} \rangle} $$
- 中序(LNR):$$ \text{\langle \text{左}, \text{根}, \text{右} \rangle} $$
- 后序(LRN):$$ \text{\langle \text{左}, \text{右}, \text{根} \rangle} $$
- 前驱后继极值结论:
- 中序前驱 \(p\)$ \text{(左子树最右下):} $\(p \to \text{rchild} == \text{NULL}\)
- 中序后继 \(q\)$ \text{(右子树最左下):} $\(q \to \text{lchild} == \text{NULL}\)
- 序列重合充要条件:
- 先序 = 中序 \(\Longleftrightarrow\) 所有非叶结点仅有右子树
- 中序 = 后序 \(\Longleftrightarrow\) 所有非叶结点仅有左子树
- 先序 = 后序 \(\Longleftrightarrow\) 树为空或仅有 1 个根结点
- 先序 = 后序逆序 \(\Longleftrightarrow\)$ \text{任意结点度数} $\(\le 1\)(单链化)
- 二叉树唯一重构组合:
- 可唯一重构:
先序 + 中序、后序 + 中序、层序 + 中序 - 不可唯一重构:
先序 + 后序(若含度为 1 结点,存在 \(2^{n_1}\)$ \text{种树形;若} $\(n_1 = 0\) 则可唯一重构) - 树与森林对应转换速记:
- 先根对先序
- 后根(中根)对中序