408 高频考点精讲:二叉树遍历(Binary Tree Traversal Applications and Expression Trees)¶
模块归属:数据结构 · 树与二叉树
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:3 次(2016~2025 年:2017#41、2022#3、2023#5)
- 历年总考查频次:4 次(含 2014#5)
- 出题形式:单项选择题(分值 2 分)与算法综合题(2017 年第 41 题,分值 15 分)兼备
- 命题特点:
- 拓扑推理维度提升:从传统的“双遍历序列重构二叉树”,深化考查“给定树形拓扑结构结合单一遍历序列逆向推导”(如 2023#5),要求考生熟练运用递归切片与子树容量推导。
- 序列邻接本质辨析:深入考查中序遍历序列中相邻结点对在二叉树拓扑结构中的相对位置约束与反例证明(如 2022#3),考查考生对中序前驱、后继判定逻辑的掌握。
- 算法设计结合表达式树:2017 年第 41 题将二叉树遍历与编译原理中的二叉表达式树(Expression Tree)紧密结合,考查中序遍历过程中对复合表达式括号化边界的处理能力。
- 知识融合度高:二叉树遍历是线索二叉树构造、二叉排序树查找判定、树与森林相互转换、图的深度优先搜索等诸多核心算法的底层基石。
二、 具体考察内容¶
1. 二叉树遍历的递归定义与代数形式化¶
二叉树遍历是指按特定搜索路径访问二叉树中所有结点,使得每个结点均被访问一次且仅被访问一次。遍历的本质是将树形非线性拓扑结构线性化映射为一维序列。
(1) 三种深度优先遍历的递归定义¶
设二叉树为 \(T\)$ \text{,其根结点为} $\(r\)$ \text{,左子树为} $\(T_L\)$ \text{,右子树为} $\(T_R\)。各序遍历的序列拼接定义如下: * 先序遍历(Pre-order Traversal): $\(\text{Preorder}(T) = \begin{cases} \emptyset, & T = \emptyset \\ \langle r \rangle \circ \text{Preorder}(T_L) \circ \text{Preorder}(T_R), & T \neq \emptyset \end{cases}\)$ * 中序遍历(In-order Traversal): $\(\text{Inorder}(T) = \begin{cases} \emptyset, & T = \emptyset \\ \text{Inorder}(T_L) \circ \langle r \rangle \circ \text{Inorder}(T_R), & T \neq \emptyset \end{cases}\)$ * 后序遍历(Post-order Traversal): $\(\text{Postorder}(T) = \begin{cases} \emptyset, & T = \emptyset \\ \text{Postorder}(T_L) \circ \text{Postorder}(T_R) \circ \langle r \rangle, & T \neq \emptyset \end{cases}\)$ 其中 \(\circ\) 表示序列的有序拼接操作。
(2) 广度优先遍历(层序遍历)¶
借助先进先出(FIFO)队列,从根结点出发,按自顶向下、自左向右的顺序访问各层结点。设当前出队结点为 \(u\),若其左孩子存在则左孩子入队,若其右孩子存在则右孩子入队,直至队列为空。
(3) 遍历复杂度分析¶
- 时间复杂度:若树中结点总数为 \(n\)$ \text{,因每个结点均被常数次访问与处理,时间复杂度为} $\(O(n)\)。
- 空间复杂度:主要取决于递归执行过程中的工作调用栈深度,其深度等于树的高度 \(h\)。
- 最好情况(平衡二叉树):\(h = \lceil \log_2(n+1) \rceil\)$ \text{,空间复杂度为} $\(O(\log n)\)。
- 最坏情况(单斜链树):\(h = n\)$ \text{,空间复杂度恶化为} $\(O(n)\)。
2. 遍历序列唯一重构二叉树定理及证明¶
(1) 双序列重构充要条件定理¶
定理:已知一棵二叉树的先序遍历序列(或后序遍历序列、层序遍历序列)与中序遍历序列,可以唯一确定这棵二叉树。
- 构造性证明(以先序 + 中序为例):
- 先序序列的第一个元素必为整棵二叉树的根结点 \(r\)。
- 在中序序列中定位元素 \(r\)$ \text{,设其下标为} $\(k\)$ \text{。由于中序序列中根结点左侧全部分布在左子树,右侧全部分布在右子树,因此中序序列被严格分割为左子树序列} $\(L_{\text{in}}\)$ \text{(长度为} $\(len_L\)$ \text{)和右子树序列} $\(R_{\text{in}}\)。
- 返回先序序列,紧跟在 \(r\)$ \text{之后的} $\(len_L\)$ \text{个结点必然构成左子树的先序序列} $\(L_{\text{pre}}\)$ \text{,剩余结点构成右子树的先序序列} $\(R_{\text{pre}}\)。
- 分别以 \((L_{\text{pre}}, L_{\text{in}})\)$ \text{和} $\((R_{\text{pre}}, R_{\text{in}})\) 为子问题进行递归划分,直至子序列长度为 0 或 1。因每一步分割均唯一且无歧义,故构成的二叉树拓扑结构唯一。
同理,后序遍历序列的末尾元素为根,层序遍历序列的首元素为根,均可结合中序序列完成左右子树的精确切片。
(2) 先序 + 后序无法唯一重构的本质原因¶
若仅已知先序序列与后序序列,不能唯一确定一棵二叉树。 * 反例与退化机理: 设先序序列为 \(\langle A, B \rangle\)$ \text{,后序序列为} $\(\langle B, A \rangle\)。 由先序首元素及后序末元素可知根为 \(A\)$ \text{,且树中仅有子结点} $\(B\)$ \text{。但结点} $\(B\)$ \text{既可以是} $\(A\)$ \text{的左孩子,也可以是} $\(A\) 的右孩子。两种形态下的遍历结果完全一致:
* 可确定拓扑的特例判定: 若二叉树中不存在度为 1 的结点(即所有非叶结点的度均为 2,称为严格二叉树或满二叉树形态),则先序序列与后序序列可以唯一确定二叉树的拓扑层次结构(但若考虑左右孩子镜像交换,左与右的具体方位判定仍需附加规定)。3. 中序遍历邻接性质定理及拓扑约束推导¶
中序遍历序列中相邻结点的空间拓扑关系是考研命题的高频理论难点(如 2022#3)。
(1) 中序前驱与中序后继定义¶
设二叉树中某结点为 \(u\): * 中序直接前驱 \(\text{pred}(u)\): - 若 \(u\)$ \text{的左子树非空,则} $\(\text{pred}(u)\) 为其左子树中最右下的结点(即沿着左孩子出发,连续向右指针寻径直至右指针为空的结点)。 - 若 \(u\)$ \text{的左子树为空,则} $\(\text{pred}(u)\)$ \text{为其沿父指针向上回溯遇到的第一个以右孩子指针包含} $\(u\)$ \text{的祖先结点;若不存在此类祖先,则} $\(u\)$ \text{无中序前驱(即} $\(u\) 为全树中序首结点)。 * 中序直接后继 \(\text{succ}(u)\): - 若 \(u\)$ \text{的右子树非空,则} $\(\text{succ}(u)\) 为其右子树中最左下的结点(即沿着右孩子出发,连续向左指针寻径直至左指针为空的结点)。 - 若 \(u\)$ \text{的右子树为空,则} $\(\text{succ}(u)\)$ \text{为其沿父指针向上回溯遇到的第一个以左孩子指针包含} $\(u\)$ \text{的祖先结点;若不存在此类祖先,则} $\(u\)$ \text{无中序后继(即} $\(u\) 为全树中序尾结点)。
(2) 中序相邻结点对 \(\langle p, q \rangle\) 的拓扑关系定理¶
定理:若二叉树中结点 \(p\)$ \text{和} $\(q\)$ \text{在中序遍历序列中相邻,且} $\(p\)$ \text{在} $\(q\)$ \text{之前(即} $\(p = \text{pred}(q)\)$ \text{且} $\(q = \text{succ}(p)\)$ \text{),则} $\(p\)$ \text{与} $\(q\) 的拓扑相对关系必然满足下列情形之一: 1. \(q\)$ \text{是} $\(p\) 的双亲: - 充分必要条件:\(p\)$ \text{是} $\(q\)$ \text{的左孩子,且} $\(p\) 没有右子树。 - 拓扑分析:遍历完 \(p\)$ \text{的左子树后访问} $\(p\)$ \text{;因} $\(p\)$ \text{无右子树,左子树遍历完毕后直接回溯访问双亲} $\(q\)$ \text{,序列表现为} $\([\dots, p, q, \dots]\)。
2. \(q\)$ \text{是} $\(p\) 的右孩子: - 充分必要条件:\(q\)$ \text{是} $\(p\)$ \text{的右孩子,且} $\(q\) 没有左子树。 - 拓扑分析:中序遍历访问完根 \(p\)$ \text{后,立即进入其右子树。因右孩子} $\(q\)$ \text{无左子树,立即访问} $\(q\)$ \text{,序列表现为} $\([\dots, p, q, \dots]\)。 3. \(q\)$ \text{是} $\(p\) 的祖先(双亲的双亲或更高阶祖先): - 充分必要条件:\(p\)$ \text{是} $\(q\)$ \text{的左子树中“最右下”的结点(且} $\(p\) 无右子树)。 - 拓扑分析:以 \(q\)$ \text{为根的左子树全部遍历完毕,最后的结点恰为} $\(p\)$ \text{;随后算法回溯至根结点} $\(q\)$ \text{,使} $\(p\)$ \text{和} $\(q\) 在序列中紧邻。 4. \(p\)$ \text{是} $\(q\) 的祖先: - 充分必要条件:\(q\)$ \text{是} $\(p\)$ \text{的右子树中“最左下”的结点(且} $\(q\) 无左子树)。 - 拓扑分析:访问完 \(p\)$ \text{后,进入其右子树一路寻径到最左侧的结点} $\(q\)$ \text{,中序遍历优先输出} $\(q\)$ \text{,使} $\(p\)$ \text{和} $\(q\) 在序列中紧邻。(3) 核心否定性定理:兄弟结点中序绝不可能相邻¶
定理:若结点 \(p\)$ \text{与结点} $\(q\)$ \text{为同一双亲的兄弟结点(即} $\(q\)$ \text{是} $\(p\)$ \text{的右兄弟),则在二叉树的中序遍历序列中,} $\(p\)$ \text{与} $\(q\) 绝对不可能相邻。
- 严格数学证明: 设 \(p\)$ \text{和} $\(q\)$ \text{的共同双亲结点为} $\(F\)。 根据二叉树的定义与分支结构,\(p\)$ \text{属于} $\(F\)$ \text{的左子树(即} $\(p \in V(T_L(F))\)),\(q\)$ \text{属于} $\(F\)$ \text{的右子树(即} $\(q \in V(T_R(F))\))。 根据中序遍历的递归定义式: $\(\text{Inorder}(F) = \text{Inorder}(T_L(F)) \circ \langle F \rangle \circ \text{Inorder}(T_R(F))\)$ 由于 \(p \in \text{Inorder}(T_L(F))\),\(q \in \text{Inorder}(T_R(F))\)$ \text{,在整体线性序列中,结点} $\(F\) 严格介于左子树序列与右子树序列之间。 因此,无论子树内部如何构成,在中序序列中 \(F\)$ \text{必排在} $\(p\)$ \text{之后、且排在} $\(q\) 之前: $$ \text{序列形态:} \quad [\dots, p, \dots, \mathbf{F}, \dots, q, \dots] $$ 由此可知,\(p\)$ \text{与} $\(q\)$ \text{之间至少间隔了一个双亲结点} $\(F\)$ \text{。故} $\(p\)$ \text{与} $\(q\) 绝不可能相邻。证毕。
4. 树形拓扑与遍历序列混合推导方法论¶
近年来考研试题倾向于给出无标号的树形拓扑结构骨架以及单一遍历序列,求解另一种遍历序列(如 2023#5)。此类题型的系统化推导方法如下:
推导流程:
[已知树形骨架] + [后序/先序序列]
│
▼
1. 根结点定位 (后序末尾 / 先序首部)
│
▼
2. 统计左右子树规模 (由树形骨架直接读取结点数 len_L, len_R)
│
▼
3. 序列切片 (根据结点数将序列无歧义拆分为左子树部分与右子树部分)
│
▼
4. 递归下推 (逐层标定每个子树的根结点与子结点身份)
│
▼
5. 按目标遍历顺序读取全树标号
- 核心理论支撑:树形拓扑确定后,二叉树每个结点的左子树结点数 \(len_L\)$ \text{和右子树结点数} $\(len_R\) 成为已知确定常数。结合遍历序列的固有相对次序,便可完全消除歧义,实现全树标号的唯一还原。
5. 二叉表达式树(Expression Tree)与中序括号化输出¶
(1) 二叉表达式树的定义与性质¶
二叉表达式树是用于存储算术或逻辑表达式的二叉树。其结构具有严格的语法语义特性: 1. 叶结点(Leaf Nodes):其度必为 0,存储操作数(如变量、常数); 2. 分支结点(Internal Nodes):其度必为 2(双目运算符)或 1(单目运算符),存储操作符(如 \(+、-、*、/\) 等); 3. 子树依赖性:以某运算符结点为根的子树,代表该运算符所作用的复合操作数(子表达式)。
(2) 三种遍历与三种表达式表示法的同构映射¶
- 先序遍历 \(\iff\) 前缀表达式(波兰式,Polish Notation):操作符位于操作数之前,如
* + a b - c d。无须括号即可无歧义反映计算顺序。 - 后序遍历 \(\iff\) 后缀表达式(逆波兰式,RPN):操作符位于操作数之后,如
a b + c d - *。天然适合借助操作数栈进行求值。 - 中序遍历 \(\iff\) 中缀表达式(Infix Notation):操作符位于操作数中间。但如果不添加括号,直接中序遍历
a + b * c - d会由于运算符默认优先级与结合律导致表达式语义发生根本性篡改。
(3) 中缀表达式输出的括号化判定规则(2017#41 核心精髓)¶
为了保证输出的中缀表达式在数学计算语义上与表达式树完全等价,必须在输出时添加括号。在 408 统考评分标准中,采用如下基于递归深度的子表达式括号化准则:
1. 根结点约束:整个表达式的最外层无须添加无意义的外层大括号;
2. 叶结点约束:单一操作数本身绝不添加括号;
3. 分支结点(运算符)约束:除了整棵树的根结点以外,每一个非根的分支结点均代表一个必须先行动作的局部复合子表达式。因此,遍历进入该分支结点的左子树前必须打印左括号 (,遍历完右子树后必须打印右括号 )。
6. 线索二叉树(Threaded Binary Tree)原理与遍历机理¶
(1) 线索化动机与指针复用¶
在含有 \(n\)$ \text{个结点的二叉链表中,每个结点具有 2 个指针域(lchild 和 rchild),全树共有} $\(2n\) 个指针。
除根结点外,树中每个结点均有一个指针指向它,故有效孩子指针数为 \(n - 1\)。
由此推导空指针域总数为:
$$ \text{空指针数} = 2n - (n - 1) = n + 1 $$
为了利用这 \(n + 1\) 个冗余空指针,引入标志位将其重构为指向该结点在前驱或后继序列中的指针,称为“线索”(Thread)。
(2) 结点存储结构定义¶
typedef struct ThreadNode {
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // tag == 0 表示孩子指针;tag == 1 表示遍历线索
} ThreadNode, *ThreadTree;
ltag == 0:lchild 指向左孩子;ltag == 1:lchild 指向前驱结点。
* rtag == 0:rchild 指向右孩子;rtag == 1:rchild 指向后继结点。
(3) 中序线索二叉树遍历算法(无栈 \(O(1)\) 空间)¶
- 求结点 \(p\) 的中序直接后继:
- 不使用工作栈的中序遍历主循环:
三、 近十年真题精讲(2016~2025)¶
【真题 1】2023 年 408 第 5 题 · 树形拓扑结构与遍历序列混合推导¶
题目
已知一棵二叉树的树形拓扑结构,若其后序遍历为 f, d, b, e, c, a,则其先序序列为( )。
A. a, e, d, f, b, c B. a, c, e, b, d, f
C. c, a, b, e, f, d D. d, f, e, b, a, c
【解析】¶
-
后序遍历特征与根结点定位: 后序遍历序列顺序为:
[左子树后序序列] [右子树后序序列] [根结点]。 已知后序序列为f, d, b, e, c, a,序列最末尾元素为a,因此全树根结点必为 a。 -
树形结构子树容量切片: 观察题干给出的树形拓扑结构:
- 根结点的右子树仅包含 1 个结点;
- 根结点的左子树包含 4 个结点。
因此,将后序序列中除去末尾根结点
a后的前 5 个元素划分为: - 左子树后序序列(前 4 个元素):
f, d, b, e -
右子树后序序列(第 5 个元素):
c由此可知,右子树即为单独结点 c。 -
左子树递归标定: 分析左子树的后序序列
f, d, b, e: - 序列末尾元素为
e,故左子树的根结点必为 e。 - 观察树形拓扑中结点
e的子树分布:e的左子树包含 2 个结点,右子树包含 1 个结点。 - 划分左子树后序序列:左分支序列为
f, d,右分支序列为b。 - 由此标定:
e的右孩子即为结点 b。 -
对于
e的左子树序列f, d:末尾元素为d,故其根为 d;树形显示该子树仅有一条左分支,故d的左孩子为 f。 -
还原后的完整二叉树结构:
-
执行先序遍历(根 -> 左 -> 右):
- 访问根结点:
a - 访问根结点的左子树(根为
e):- 访问
e - 访问
e的左子树(根为d): - 访问
d - 访问
d的左孩子f - 访问
e的右孩子b
- 访问
- 访问根结点的右子树:
c拼接得到完整的先序遍历序列:a, e, d, f, b, c。
正确答案:A
【真题 2】2022 年 408 第 3 题 · 中序遍历序列相邻结点拓扑约束判定¶
题目
若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻,且 p 在 q 之前,则下列 p 与 q 的关系中,不可能的是( )。
I. q 是 p 的双亲
II. q 是 p 的右孩子
III. q 是 p 的右兄弟
IV. q 是 p 的双亲的双亲
A. 仅 I B. 仅 III C. 仅 II, III D. 仅 II, IV
【解析】¶
在中序遍历中,访问序列满足顺序:[左子树] -> [根] -> [右子树]。题目条件为中序序列中 \(p\)$ \text{紧挨在} $\(q\)$ \text{之前,记作} $\(\langle \dots, p, q, \dots \rangle\)。逐项构造验证拓扑关系:
-
命题 I 判定(可能成立): 若 \(q\)$ \text{是} $\(p\)$ \text{的双亲,构造二叉树:} $\(p\)$ \text{是} $\(q\)$ \text{的左孩子,且} $\(p\) 没有右子树。
中序遍历顺序为:访问 \(p\)$ \text{的左子树(空)} $\(\to\)$ \text{访问根} $\(p\) \(\to\)$ \text{访问} $\(p\)$ \text{的右子树(空)} $\(\to\)$ \text{回溯访问双亲} $\(q\)。 此时中序序列输出为 \(\langle p, q \rangle\),\(p\)$ \text{与} $\(q\)$ \text{相邻且} $\(p\)$ \text{在} $\(q\) 之前。命题 I 可能成立。 -
命题 II 判定(可能成立): 若 \(q\)$ \text{是} $\(p\)$ \text{的右孩子,构造二叉树:} $\(q\)$ \text{是} $\(p\)$ \text{的右孩子,且} $\(q\) 没有左子树。
中序遍历顺序为:访问 \(p\)$ \text{的左子树(空)} $\(\to\)$ \text{访问根} $\(p\) \(\to\)$ \text{进入右子树访问} $\(q\)$ \text{(其左子树为空直接输出} $\(q\))。 此时中序序列输出为 \(\langle p, q \rangle\),\(p\)$ \text{与} $\(q\)$ \text{相邻且} $\(p\)$ \text{在} $\(q\) 之前。命题 II 可能成立。 -
命题 IV 判定(可能成立): 若 \(q\)$ \text{是} $\(p\)$ \text{的双亲的双亲(即祖父结点),构造二叉树:} $\(q\)$ \text{的左孩子为} $\(x\),\(x\)$ \text{的右孩子为} $\(p\)$ \text{,且} $\(p\) 没有右子树。
中序遍历顺序:进入 \(q\)$ \text{的左子树} $\(\to\)$ \text{访问} $\(x\) \(\to\)$ \text{进入} $\(x\)$ \text{的右子树访问} $\(p\) \(\to\)$ \text{整个左子树遍历完毕} $\(\to\)$ \text{回溯访问根结点} $\(q\)。 中序序列表现为 \(\langle x, p, q \rangle\)$ \text{,此时} $\(p\)$ \text{与} $\(q\)$ \text{相邻且} $\(p\)$ \text{在} $\(q\) 之前。命题 IV 可能成立。 -
命题 III 判定(绝对不可能成立): 若 \(q\)$ \text{是} $\(p\)$ \text{的右兄弟,设二者的共同双亲为} $\(F\)。
根据二叉树中序遍历的严格递归定义: - 必须首先遍历完双亲 \(F\)$ \text{的整个左子树(结点} $\(p\) 属于该左子树);
- 随后必须访问双亲结点 \(F\) 本身;
- 最后才能进入双亲 \(F\)$ \text{的右子树进行遍历(结点} $\(q\) 属于该右子树)。 因此,双亲结点 \(F\)$ \text{在线性序列中必然严格位于} $\(p\)$ \text{与} $\(q\) 之间,遍历序列必然呈现为: $\([\dots, p, \dots, \mathbf{F}, \dots, q, \dots]\)$ \(p\)$ \text{与} $\(q\)$ \text{之间至少存在一个结点} $\(F\),两者绝对不可能在中序遍历序列中相邻。故命题 III 绝对不可能成立。
综上分析,不可能的仅有 III。
正确答案:B
【真题 3】2017 年 408 第 41 题 · 表达式树转换为等价中缀表达式算法设计¶
题目
请设计一个算法,将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。
二叉树结点定义如下:
(1) 给出算法的基本设计思想。
(2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
【解析】¶
(1) 基本设计思想¶
表达式树与中缀表达式具有天然的对应关系,表达式树的中序遍历序列对应中缀表达式的操作数与操作符排列次序。然而,由于算术运算符存在运算优先级与结合顺序,直接进行中序遍历会丢失运算次序,必须通过添加圆括号来保证逻辑等价性。
观察表达式树输出中缀表达式时的加括号规律:
1. 根结点特征:整棵树的根结点对应整个表达式最后执行的外层运算符,其外层无须添加圆括号。
2. 叶结点特征:叶结点均为单一操作数(常数或变量),不需要添加括号。
3. 分支结点特征:除根结点外,树中所有的分支结点均代表优先计算的复合子表达式。因此,必须在开始遍历该子树(即遍历其左子树)之前输出左括号 (,并在遍历完该子树(即遍历其右子树)之后输出右括号 )。
算法采用基于递归深度的中序遍历策略:
定义递归函数 BtreeToInfix(BTree *root, int depth),其中参数 depth 表示当前结点在树中所处的深度,初始调用时根结点的深度设为 1。
- 若当前结点为空,直接返回。
- 若当前结点为非根结点的分支结点(判定条件:depth > 1 且当前结点的左右孩子至少有一个非空),则先输出左括号 (。
- 递归遍历左子树:BtreeToInfix(root->left, depth + 1)。
- 输出当前结点的存储内容 root->data。
- 递归遍历右子树:BtreeToInfix(root->right, depth + 1)。
- 若当前结点为非根结点的分支结点,输出右括号 )。
(2) 算法代码实现(C 语言)¶
#include <stdio.h>
#include <stdbool.h>
// 辅助递归函数:depth 记录当前结点的递归深度
void BTreeToInfixExp(BTree *root, int depth) {
if (root == NULL) {
return; // 空结点直接返回
}
// 判断当前结点是否为分支结点 (操作符)
bool isOperator = (root->left != NULL || root->right != NULL);
// 规则:非根结点的分支结点,在进入子表达式前输出左括号
if (depth > 1 && isOperator) {
printf("(");
}
// 递归遍历左子树
BTreeToInfixExp(root->left, depth + 1);
// 输出当前结点存储的操作数或操作符
printf("%s", root->data);
// 递归遍历右子树
BTreeToInfixExp(root->right, depth + 1);
// 规则:非根结点的分支结点,在退出子表达式后输出右括号
if (depth > 1 && isOperator) {
printf(")");
}
}
// 题目要求的对外统一接口函数
void BtreeToExp(BTree *root) {
// 根结点深度初始化为 1
BTreeToInfixExp(root, 1);
}
(3) 算法复杂度分析¶
- 时间复杂度:算法基于中序遍历框架,树中的每一个结点被常数次访问和输出。若树中结点总数为 \(n\)$ \text{,则时间复杂度为} $\(O(n)\)。
- 空间复杂度:空间开销取决于递归调用栈的深度,等于二叉树的高度 \(h\)$ \text{。在最坏情况下(树退化为单链),空间复杂度为} $\(O(n)\)$ \text{;在树保持形态平衡时,空间复杂度为} $\(O(\log n)\)。
四、 核心解题套路与易错陷阱¶
1. 遍历序列重构与切片分治三步法¶
在求解给定遍历序列还原二叉树的选择题时,避免在草稿纸上盲目尝试拼凑,应当使用标准化的分治切片法:
步骤 1: 定根
先序序列首元素 / 后序序列末元素 / 层序序列首元素 ──> 锁定当前子树的根结点 R。
步骤 2: 切片
在中序序列中找到 R 的位置:
[ 中序左子树序列 ] R [ 中序右子树序列 ]
│ │
长度为 len_L 长度为 len_R
步骤 3: 分流
将先序或后序序列严格按 len_L 和 len_R 斩断划分:
先序: R [ 连续 len_L 个为左先序 ] [ 剩余 len_R 个为右先序 ]
后序: [ 连续 len_L 个为左后序 ] [ 紧随 len_R 个为右后序 ] R
对左右子序列递归执行上述步骤。
2. 遍历序列相邻性判定的一般性排查法则¶
对于考查遍历序列中相邻结点 \(\langle p, q \rangle\)(\(p\)$ \text{紧靠在} $\(q\) 前方)拓扑关系的选择题,可直接套用如下排查准则:
| 遍历序列类型 | 相邻形式 | 成立的拓扑相对关系典型范式 | 绝对不可能成立的关系 |
|---|---|---|---|
| 中序遍历 | \(p\)$ \text{紧挨在} $\(q\)$ \text{前 | 1.} $\(q\)$ \text{是} $\(p\)$ \text{的双亲(} $\(p\)$ \text{无右子树) 2.} $\(q\)$ \text{是} $\(p\)$ \text{的右孩子(} $\(q\)$ \text{无左子树) 3.} $\(q\)$ \text{是} $\(p\)$ \text{的高阶祖先(} $\(p\)$ \text{是} $\(q\)$ \text{左子树最右下结点) |
} $\(q\)$ \text{是} $\(p\) 的右兄弟(双亲必插在二者中间阻断) |
| 先序遍历 | \(p\)$ \text{紧挨在} $\(q\)$ \text{前 | 1.} $\(q\)$ \text{是} $\(p\)$ \text{的左孩子 2.} $\(q\)$ \text{是} $\(p\)$ \text{的右孩子(} $\(p\)$ \text{无左子树) 3.} $\(q\)$ \text{是} $\(p\)$ \text{的右兄弟(} $\(p\)$ \text{为左叶子结点) |
} $\(q\)$ \text{是} $\(p\) 的双亲(先序中双亲必在孩子之前访问) |
| 后序遍历 | \(p\)$ \text{紧挨在} $\(q\)$ \text{前 | 1.} $\(p\)$ \text{是} $\(q\)$ \text{的右孩子 2.} $\(p\)$ \text{是} $\(q\)$ \text{的左孩子(} $\(q\)$ \text{无右子树) 3.} $\(p\)$ \text{是} $\(q\)$ \text{的左兄弟(} $\(p\)$ \text{为右叶子结点) |
} $\(p\)$ \text{是} $\(q\) 的双亲(后序中双亲必在孩子之后访问) |
3. 高频易错陷阱防范¶
陷阱 1:表达式树中缀转换的最外层冗余括号¶
- 错误表现:直接对所有运算符结点打印括号,导致形如
(a + b) * c的表达式被输出为((a + b) * c)。 - 规避法则:必须引入
depth(根为 1)或者引入双亲判断指针。根结点决不可打印最外层括号,否则在统考评分标准中会被扣除 2~3 分。
陷阱 2:混淆中序相邻与兄弟关系¶
- 错误表现:认为“既然 \(p\)$ \text{是左孩子,} $\(q\) 是右孩子,遍历完左孩子立刻遍历右孩子,所以相邻”。
- 规避法则:牢记中序遍历口诀“左-根-右”。访问完左子树后,必须先返回双亲根结点,随后才能转向右子树。双亲在序列中起到天然的物理隔离作用。
陷阱 3:线索二叉树遍历时的死循环与野指针¶
- 错误表现:在线索二叉树非递归遍历代码中,错误地将
p = p->rchild作为步进条件,忽略了rtag标志位的检查。 - 规避法则:只有当
rtag == 1时,rchild才是直接线索后继;当rtag == 0时,rchild指向真实右孩子,后继必须通过FirstNode(p->rchild)在右子树中寻径到最左下结点。
五、 考点速记清单¶
- 唯一重构法则:中序是核心。先序+中序、后序+中序、层序+中序均可唯一重构二叉树;先序+后序不可唯一重构。
- 中序相邻铁律:兄弟绝不相邻(双亲必在其中);中序相邻只发生在“父子直接相连”或“沿子树单向寻径至最外侧折返”的祖先后代之间。
- 表达式树映射:
- 先序 \(\to\) 前缀式(波兰式);
- 中序 \(\to\) 中缀式(必须配合括号);
- 后序 \(\to\) 后缀式(逆波兰式)。
- 中缀括号化标准范式:非根、非叶的分支结点,在左子树遍历前加
(,在右子树遍历后加)。 - 线索二叉树空间复杂度:\(n\)$ \text{个结点的二叉树含} $\(n + 1\)$ \text{个空指针。中序线索遍历无须栈,空间复杂度降至} $\(O(1)\)。