Lab 04-T-03：中序遍历理论题精练

目标

独立辨析中序遍历中的核心概念、结构性质与遍历关系；
对选择题写出排除干扰项的依据，而不只记忆答案字母；
对源文档提供的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读第 4 章对应教材，再开始本组练习。

环境、输入与预期输出

环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
输入：11 道四选一选择题，3 道综合题。
预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

选择题先独立判断并记录依据，再点击“提交答案”；
提交后核对正确答案和解析，做错的题使用“重新作答”；
综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
对重复出现的真题，说明它在不同知识主题下分别考查了什么。

选择题

答题进度已答 0/11正确 0

第 1 题

难度★★考点前序遍历、中序遍历、二叉树基础（性质+存储）、二叉树遍历、先序遍历

要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是( )。

只有左子树

只有右子树

结点的度均为 1

结点的度均为 2

第 2 题

难度★★★★考点二叉树基础（性质+存储）、中序遍历、二叉树、相邻结点关系

若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻，且 p 在 q 之前，则下列 p 与 q 的关系中，不可能的是( )。

I. q 是 p 的双亲

II. q 是 p 的右孩子

III. q 是 p 的右兄弟

IV. q 是 p 的双亲的双亲

仅 I

仅 III

仅 II、III

仅 II、IV

第 3 题

难度★★★★考点二叉树基础（性质+存储）、中序遍历、线索二叉树、二叉树、前驱后继

p、q、v 都是二叉树 T 中的结点，二叉树 T 的中序遍历为 ···, p，v，q，··· ，其中 v 有两个孩子结点，则下列说法正确的是( )。

p 没右孩子，q 没左孩子

p 没右孩子，q 有左孩子

p 有右孩子，q 没左孩子

p 有右孩子，q 有左孩子

第 4 题

难度★★考点中序遍历、二叉树遍历、递归

对下列二叉树进行中序遍历，输出序列是( )。

A(B(D, E(G, _)), C(_, F))

D, B, G, E, A, C, F

A, B, D, E, G, C, F

D, G, E, B, F, C, A

A, B, C, D, E, F, G

第 5 题

难度★★★考点中序遍历、非递归、栈、算法步骤

用栈实现中序遍历的非递归算法：从根开始一直向左走直到 NULL（路径上每个结点都压栈）；然后 pop 栈顶并访问、再转向该结点的右子树重复同样过程；栈空且当前结点为 NULL 时结束。下列伪代码正确的是( )。

v=root; while(v || !empty){ while(v){push(v); v=v.left;} v=pop(); visit(v); v=v.right; }

push(root); while(!empty){ v=pop(); visit(v); if(v.left)push(v.left); if(v.right)push(v.right); }

v=root; while(v || !empty){ if(v){push(v); v=v.left;} else{ v=pop(); v=v.right; visit(v); } }

push(root); while(!empty){ v=top(); if(v.left)push(v.left); else{ visit(v); v=pop(); v=v.right; } }

第 6 题

难度★★★考点中序遍历、BST、升序性质

关于"BST（二叉搜索树）的中序遍历必为升序序列"这一性质，下列说法正确的是( )。

这一性质仅对完美BST 成立；非完美 BST 中序可能乱序

这一性质对任何 BST 都成立，与 BST 的形态无关

这一性质对完全二叉树都成立，不局限于 BST

BST 的中序遍历是降序，前序遍历才是升序

第 7 题

难度★★★★考点中序遍历、二叉树构造、前序+中序

已知一棵二叉树的中序遍历为 $D, B, G, E, A, C, F$ 、前序遍历为 $A, B, D, E, G, C, F$ 。该二叉树的后序遍历是( )。

D, G, E, B, F, C, A

D, B, G, E, A, C, F

F, C, A, E, G, B, D

A, B, D, E, G, C, F

第 8 题

难度★★★★考点中序遍历、非递归、栈深度

用栈实现中序遍历的非递归算法（参见 002 题），对二叉树 A(B(D, E(G, _)), C(_, F)) 执行该算法，栈在整个遍历过程中的最大深度是( )。

第 9 题

难度★★★★考点中序遍历、线索化、中序后继

关于"中序线索二叉树"与中序遍历的关系，下列说法正确的是( )。

中序线索二叉树是把二叉树中空指针用"中序前驱 / 中序后继"指针替代得到的——左空指针指中序前驱，右空指针指中序后继（中序首结点的左空、末结点的右空保留为空或指向头结点）

中序线索化要新增

n

个指针字段（每个结点 +1 个）

在中序线索二叉树中，查找任意结点的中序后继的时间复杂度都是

O (1)

中序线索二叉树等价于把所有结点按中序顺序串成的单链表

第 10 题

难度★★★★★考点中序遍历、综合性质

关于二叉树中序遍历的下列说法，全部正确的选项是( )。

① 中序遍历的非递归算法需要使用栈。 ② BST 的中序遍历输出严格升序；反之，任何键值互异的二叉树，若其中序输出严格升序，则该二叉树必为 BST。 ③ 中序遍历 + 前序遍历可唯一确定一棵二叉树；中序 + 后序也可唯一确定。 ④ 中序遍历的第一个输出是整棵树的最左下结点（不一定是叶子但一定无左孩）。

①②③

①②③④

①③④

②③④

第 11 题

难度★★★考点中序遍历、遍历次序、祖先与子孙、最近公共祖先、投影性质

设 $n$ 、 $m$ 为一棵二叉树上的两个结点。按标准画法把该二叉树画在平面上（每个结点的左子树画在其左下方、右子树画在其右下方），则在中序遍历时， $n$ 在 $m$ 前的条件是（）。

n

在

m

左方

n

是

m

的祖先

n

在

m

右方

n

是

m

的子孙

答案总览（建议完成全部题目后查看）

第 1 题：B
第 2 题：B
第 3 题：A
第 4 题：A
第 5 题：A
第 6 题：B
第 7 题：A
第 8 题：B
第 9 题：A
第 10 题：D
第 11 题：A

综合题

综合题 1｜2017 年真题第 41 题

难度：★★★★ · 分值：15 分

考点：树与森林、中序遍历、表达式树、中缀表达式、算法设计

请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，下列两棵表达式树作为算法输入时，输出的中缀表达式分别为 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))。

表达式树 1（中缀：(a+b)*(c*(-d))）：

text

*(+(a, b), *(c, -(_, d)))

表达式树 2（中缀：(a*b)+(-(c-d))）：

text

+(*(a, b), -(_, -(c, d)))

注：单目运算符 -（取负）在树里以左子树为空 _、右子树为操作数表示。

二叉树结点的定义如下：

typedef struct node {
    char data[10];   // 存储操作数或操作符
    struct node *left, *right;
} BTree;

要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

参考答案与详细解析

详细解析

(1) 设计思想

答案：对表达式树做中序遍历——访问内部结点（操作符）时先输出 (、再递归左、再输出该操作符、再递归右、最后输出 )；叶结点（操作数）直接输出。但根结点外面不加括号。

为什么是"中序 + 加括号"？

中缀表达式天生就是表达式树的中序遍历。问题在于"括号"——比如 a+b*c 和 (a+b)*c 的中序遍历都是 a+b*c，但树结构不同。要无歧义还原算式，每个非叶子树都用一对括号"封装"自己就万无一失。

根不加括号的两个原因：

整个式子最外层无需括号（题面例子也没有）；
若递归时一上来就给根加括号，单目 - 会产生 (-d) 整体在最外层，看起来变扭。

单目 -（取负）的处理：题中约定单目 - 的左子树为空、右子树为操作数。算法天然支持——递归"左子树"时若是空指针就跳过、不递归；输出顺序变成 ( - X )，正合题意（如 (-d)）。

完整流程：

递归参数：当前结点 node、当前递归深度 depth（根 depth=0，子树 depth>0）；
若 node 为空：直接 return；
若 node 是叶子：输出 node->data，return；
否则（操作符）：
- 若 depth > 0：输出 (；
- 递归左子树（若不空）；
- 输出 node->data（操作符本身）；
- 递归右子树；
- 若 depth > 0：输出 )。

(2) 代码实现

typedef struct node {
    char data[10];
    struct node *left, *right;
} BTree;

// depth: 当前结点在树中的递归深度，根为 0
static void traverse(BTree *node, int depth, char *buf) {
    if (node == NULL) return;

    int isLeaf = (node->left == NULL && node->right == NULL);
    if (isLeaf) {
        strcat(buf, node->data);                     // 操作数直接输出
        return;
    }

    if (depth > 0) strcat(buf, "(");                 // 非根的操作符，左侧加 (
    if (node->left != NULL) traverse(node->left, depth + 1, buf);
    strcat(buf, node->data);                         // 输出操作符
    traverse(node->right, depth + 1, buf);
    if (depth > 0) strcat(buf, ")");                 // 非根的操作符，右侧加 )
}

void toInfix(BTree *root, char *buf) {
    buf[0] = '\0';
    traverse(root, 0, buf);
}

用例 1 推导——*(+(a, b), *(c, -(_, d)))：

递归状态	输出累计
进根 `*`，depth=0，不加 (	``
递归左子树 `+`，depth=1，加 (	`(`
递归 `a`（叶）输出 a	`(a`
输出 `+`	`(a+`
递归 `b`（叶）输出 b	`(a+b`
`+` 子树结束，加 )	`(a+b)`
输出根 `*`	`(a+b)*`
递归右子树 `*`，depth=1，加 (	`(a+b)*(`
递归 `c`（叶）	`(a+b)*(c`
输出 `*`	`(a+b)(c`
递归右孙 `-`（单目），depth=2，加 (	`(a+b)(c(`
左子空，跳过	`(a+b)(c(`
输出 `-`	`(a+b)(c(-`
递归 `d`（叶）	`(a+b)(c(-d`
`-` 子树结束，加 )	`(a+b)(c(-d)`
`*` 子树结束，加 )	`(a+b)(c(-d))`

✓ 与题面一致。

关键点说明：

括号成对出现的位置：进入非叶非根时加 (，离开非叶非根时加 )，绝对配对，不会少一只多一只。
单目 - 不需特殊代码：题中规定单目 - 的左子树为空，递归 left 时直接 node == NULL return；接着输出 - 再递归右就得到 (-X)，与"先 ( 再 op 再右子树再 )"流水线一致。
复杂度：时间 O(n)（n 个结点各访问一次，strcat 单次累加是常数次字符）；空间 O(h)（递归栈深 = 树高）。

综合题 2｜2022 年真题第 41 题

难度：★★★★ · 分值：13 分

考点：二叉搜索树、中序遍历、顺序存储、算法设计

已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE 为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int      ElemNum;               // 实际占用的数组元素个数
} SqBiTree;

T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。例如，对于两棵非空二叉树 T₁ 和 T₂：

二叉树 T₁（满足 BST 定义）：

text

40(25(_, 30(27, _)), 60(_, 80))

二叉树 T₂（不满足 BST 定义）：

text

40(50(_, 30(_, 35)), 60)

T₁ 和 T₂ 对应的顺序存储如下（位置从下标 0 起，1-indexed 的层序位置规则：父 i 的左孩子在 2i+1、右孩子在 2i+2）：

数组	内容（依次）	ElemNum
`T₁.SqBiTNode`	`[40, 25, 60, -1, 30, -1, 80, -1, -1, 27]`	10
`T₂.SqBiTNode`	`[40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35]`	11

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是则返回 true，否则返回 false。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

参考答案与详细解析

详细解析

(1) 设计思想

答案：对顺序存储的二叉树做中序遍历，维护"上一个访问的值" prev。中序序列必须严格递增（即每次访问的当前值 > prev）；任何一处 cur ≤ prev 就直接判定不是 BST。

两个关键点：

BST 中序遍历严格递增——这是 BST 的等价定义之一。注意必须严格 >，因为题中说"结点值均为正整数"且 BST 通常默认无重复。
顺序存储下父子关系：下标 $i$ 的左孩子在 $2 i + 1$ ，右孩子在 $2 i + 2$ ；越界（ $i \geq ElemNum$ ）或值为 $- 1$ 表示该子树为空，直接返回当作合法。

流程：

初始化 prev = -∞；
从下标 0（根）开始递归中序：先递归左子树（ $2 i + 1$ ）→ 检查并更新 prev → 再递归右子树（ $2 i + 2$ ）；
任一步发现 cur ≤ prev 立即返回 false；走完所有结点未触发返回 true。

(2) 代码实现

typedef struct {
    int SqBiTNode[MAX_SIZE];
    int ElemNum;
} SqBiTree;

static int prev_val;        // 上一次中序访问到的值，全局便于递归
static int g_ok;            // 当前判定结果

static void inorderCheck(SqBiTree T, int i) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1 || !g_ok) return;
    inorderCheck(T, 2*i + 1);                      // 左子树
    if (T.SqBiTNode[i] <= prev_val) {              // 当前必须严格大于 prev
        g_ok = 0;
        return;
    }
    prev_val = T.SqBiTNode[i];                     // 更新 prev
    inorderCheck(T, 2*i + 2);                      // 右子树
}

int isBST(SqBiTree T) {
    prev_val = INT_MIN;                            // 第一个被访问的结点没有"上一个"，用 -∞
    g_ok = 1;
    inorderCheck(T, 0);
    return g_ok;
}

关键点说明：

prev 必须是引用语义（这里用 static）：递归中"上一个值"贯穿整次遍历，不能传值副本——否则左子树更新的 prev 进不了右子树。考场里若不想用 static 全局，可以改成传指针 int *prev。
-1 与越界都是空子树：进入递归先判这两条退出条件，避免对不存在的结点取值或继续递归。
触发不合法后立刻短路：检查 !g_ok 提前 return，避免后续递归还在更新 prev、扫描无意义。
复杂度：时间 O(n)，每个数组位置最多访问一次（n 是 ElemNum）；空间 O(h)，递归栈深度等于树高，最坏 O(n)。

编者注（生僻术语）：题目说"二叉树 T 中不存在的结点用 -1 表示"——这是顺序存储二叉树的标准约定。本题考点是顺序存储下的中序遍历：链式结构遍历谁都会，但顺序结构下要现场推导父子下标公式（2i+1 / 2i+2），这是真正的得分点。

综合题 3｜巩固题

难度：★★★★ · 分值：15 分

考点：中序遍历、二叉树、非递归、显式栈、算法设计

设二叉树 T 以二叉链表存储，结点结构如下：

typedef struct BiTNode {
    int             data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

T 指向二叉树的根（空树以 T == NULL 表示）。请按下列三项分别完成：

(1) 给出非递归中序遍历算法的基本设计思想（用显式栈模拟递归过程，禁止使用系统递归调用）。

(2) 采用 C 语言描述该非递归算法，关键之处给出注释。函数把中序遍历得到的各结点 data 依次写入 out[]，并返回写入个数（即树的结点数）。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

函数签名（与 OJ wrapper 一致）：

int inorderTraverse(BiTree T, int out[]);

约束： $0 \leq n \leq 1000$ ；时间复杂度 $O (n)$ ；空间复杂度 $O (h)$ （ $h$ 为树高，对应显式栈最大深度；不计输入与输出数组）。

测试覆盖维度：测试用例除常规情况外，还包含以下边界，WA 时建议逐个排查：

空树（ $n = 0$ ）：返回 0，不写入 out；
单节点树（ $n = 1$ ）：返回 1，out[0] = 根的 data；
左偏链（每个非叶结点仅有左孩子）：中序结果 = 链尾到链头逆序排列；
右偏链（每个非叶结点仅有右孩子）：中序结果 = 链头到链尾顺序排列；
完全二叉树：中序对应"中序层次"，非简单的层序；
接近 $n_{max} = 1000$ 的中等规模：验证显式栈深度边界（栈容量声明须够大）。

参考答案与详细解析

详细解析

思路分析

中序遍历的递归定义是「左 → 根 → 右」三步走：先递归遍历左子树，再访问当前根，最后递归遍历右子树。把递归改写为非递归的标准做法是用显式栈接管系统调用栈——把"待访问的祖先节点"按"后入先出"的顺序自己保管起来。

解法 1（朴素错路）：层序遍历过程中按位置分类

考生看到"遍历二叉树"会本能地想到层序遍历的队列模板：弹出节点 → 把孩子入队。试图改造成中序时容易写出"先把左孩子入队，再访问当前节点，再把右孩子入队"——但队列是 FIFO，导致左子树还没访问完时根就已经被处理掉了，根本无法表达"先遍历完整个左子树再回头访问根"这个语义。这条路必然失败。

解法 2（最优）：显式栈，沿左链入栈、出栈访问、转右子树

把递归过程在脑中跑一遍可以看到，递归栈里保存的恰好是"当前节点到根的所有祖先"。把这条信息搬到显式栈里就有了下列三步式循环模板：

模板（408 教材标准）：

设栈 S，指针 p ← T；
while (p ≠ NULL 或 S 非空) {
    while (p ≠ NULL)            // ① 沿左链走到底，每步入栈
        S.push(p);  p ← p.lchild;
    p ← S.pop();                // ② 弹栈访问（这是中序应访问的位置）
    output(p.data);
    p ← p.rchild;               // ③ 转向右子树，下一轮继续①
}

为什么"沿左链入栈、出栈访问、转右子树"等价于中序（命题人复盘）：

回到中序递归定义「左 → 根 → 右」，需要观察一个等价改写——「中序(T) = 中序(T.lchild) + visit(T) + 中序(T.rchild)」可以递归展开为「中序(T.lchild.lchild) + visit(T.lchild.lchild.lchild...) + ... + visit(T.lchild) + visit(T) + 中序(T.rchild)」。也就是说，任何节点被访问之前，它的所有左祖先必须先被访问；而在到达"最左节点"之前，沿途所有节点（包括根）必须先被记住——这正是步骤 ① 沿左链入栈的语义。

到达最左空指针时，栈顶恰是"应当访问的下一个节点"（左子树已空 ⇒ 左部分已完成）——出栈 + 输出（步骤 ②）。接着按递归定义还要处理该节点的右子树——把 p 指向 rchild，回到外层循环重新执行步骤 ①（步骤 ③）。终止条件「p == NULL 且栈空」表示没有未处理的子树也没有待访问的祖先，遍历完成。

与递归的等价性论证

设递归中序遍历的输出序列为 $σ_{r}$ ，非递归输出序列为 $σ_{i}$ 。对树的结点数 $n$ 用强归纳：

基底（ $n = 0$ ）：递归直接 return， $σ_{r}$ 为空；非递归外层 while 条件 p == NULL && stack empty 不成立，循环不进入， $σ_{i}$ 也为空。✓
归纳步（ $n \geq 1$ ）：设当前根为 $r$ ，左子树有 $n_{L}$ 个结点，右子树有 $n_{R}$ 个结点（ $n_{L} + n_{R} = n - 1$ ，均 $< n$ ）。
- 递归： $σ_{r} = σ_{r} (L) + [r] + σ_{r} (R)$ 。
- 非递归：从根 $r$ 开始沿左链入栈直到最左空——此过程把 $L$ 的"左脊"全部压入栈底之上。断言：随后弹出与转右、再次沿左链入栈的全过程，等价于在子树 $L$ 上独立跑一遍非递归中序，最终输出 $σ_{i} (L)$ ，然后栈顶变为 $r$ 、弹出 $r$ 输出 $[r]$ ，最后 $p \leftarrow r . rchild$ 进入右子树等价于在子树 $R$ 上独立跑一遍非递归中序，输出 $σ_{i} (R)$ 。这是因为子树外的栈底元素不影响子树内的入栈出栈次序——栈的 LIFO 隔离了不同子树的访问轨迹。
- 因此 $σ_{i} = σ_{i} (L) + [r] + σ_{i} (R)$ 。
- 由归纳假设 $σ_{i} (L) = σ_{r} (L)$ 、 $σ_{i} (R) = σ_{r} (R)$ ，故 $σ_{i} = σ_{r}$ 。✓

结论：两种实现产出完全相同的中序序列。

参考实现（C）

int inorderTraverse(BiTree T, int out[]) {
    int cnt = 0;
    /* 显式栈：最大深度 = 树高，本题 n ≤ 1000 故栈容量 1024 已够 */
    BiTNode *stack[1024];
    int top = -1;
    BiTNode *p = T;

    while (p != NULL || top >= 0) {
        /* ① 沿左链走到底，沿途入栈（"记住"所有左祖先） */
        while (p != NULL) {
            stack[++top] = p;
            p = p->lchild;
        }
        /* ② 弹栈访问（左子树已空 ⇒ 栈顶就是中序应输出的节点） */
        p = stack[top--];
        out[cnt++] = p->data;
        /* ③ 转向右子树，下一轮回到 ① 沿其左链入栈 */
        p = p->rchild;
    }
    return cnt;
}

关键点说明：

外层条件 p != NULL || top >= 0 缺一不可：刚弹完根、p 指向根的右子树时，p 可能非空但栈可能空——此时必须靠 p != NULL 让循环继续；反之中途某次右子树处理完后 p == NULL 但栈非空——靠 top >= 0 让循环继续弹出更上层的祖先。两个条件用 || 连接，缺一会提前停。
内层 while (p != NULL) 一定要把"沿左链入栈"走到底：常见错写"if (p != NULL) stack[++top] = p; p = p->lchild;"只入栈一次就停——这样只能记住根的左孩子，记不住"左孩子的左孩子……"。
stack[1024] 的容量推导：题面声明 $n \leq 1000$ ，左偏链场景下栈深 = $n$ ，故 1024 余量充足；不可写成 stack[100] 或不声明大小。

递归实现作为对照：仅供学生对照、不作 OJ 提交，最短形态为

void inorderRec(BiTree T, int out[], int *cnt) {
    if (T == NULL) return;
    inorderRec(T->lchild, out, cnt);
    out[(*cnt)++] = T->data;
    inorderRec(T->rchild, out, cnt);
}

与非递归输出完全一致（前述等价性论证已证）。

例：在具体二叉树上 trace 非递归过程

设二叉树形如：

text

1(2(4, 5), 3(_, 6))

中序遍历期望输出：4 2 5 1 3 6。下表每行记录一次"入栈"或"出栈"事件后栈的状态与累计输出。栈底在左、栈顶在右，p 列表示该步操作完成后 p 指向的节点（∅ 表示 NULL）。

步骤	操作	`p`	栈（底→顶）	累计输出
1	入栈 1，`p ← 1.lchild`	2	`[1]`	``
2	入栈 2，`p ← 2.lchild`	4	`[1, 2]`	``
3	入栈 4，`p ← 4.lchild`	∅	`[1, 2, 4]`	``
4	出栈 4，输出 4，`p ← 4.rchild`	∅	`[1, 2]`	`4`
5	出栈 2，输出 2，`p ← 2.rchild`	5	`[1]`	`4 2`
6	入栈 5，`p ← 5.lchild`	∅	`[1, 5]`	`4 2`
7	出栈 5，输出 5，`p ← 5.rchild`	∅	`[1]`	`4 2 5`
8	出栈 1，输出 1，`p ← 1.rchild`	3	`[]`	`4 2 5 1`
9	入栈 3，`p ← 3.lchild`	∅	`[3]`	`4 2 5 1`
10	出栈 3，输出 3，`p ← 3.rchild`	6	`[]`	`4 2 5 1 3`
11	入栈 6，`p ← 6.lchild`	∅	`[6]`	`4 2 5 1 3`
12	出栈 6，输出 6，`p ← 6.rchild`	∅	`[]`	`4 2 5 1 3 6`
13	`p == NULL` 且栈空，循环结束	∅	`[]`	`4 2 5 1 3 6` ✓

观察两条规律可校验自己写的 trace：

每个结点恰好被入栈一次、出栈一次：n 个结点共 2n 次栈操作，与下方时间复杂度 $O (n)$ 一致；
每次"出栈"事件触发一次输出：输出序列长度 = 出栈次数 = 结点数 n。

复杂度证明

时间复杂度 $O (n)$ ：

每个结点恰好被入栈一次（在步骤 ① 沿左链下行时）、出栈一次（在步骤 ② 弹栈访问时）、其 rchild 被访问一次（在步骤 ③ 进入下一轮时）。设 $n$ 为结点数：

T (n) = \underset{入栈}{\underset{⏟}{n}} + \underset{出栈}{\underset{⏟}{n}} + \underset{rchild 访问}{\underset{⏟}{n}} + O (1) \cdot n = O (n)

每帧循环体内只有常数次比较、赋值与数组写入，无嵌套乘法因子。

空间复杂度 $O (h)$ ：

显式栈是唯一的空间开销。栈中元素是"当前节点到根的所有左祖先"——任意时刻栈深 $\leq$ 该路径长度 $\leq$ 树高 $h$ 。

最好情况（完全平衡树）： $h = ⌈ \log_{2} (n + 1) ⌉$ ，栈深 $O (\log n)$ ；
最坏情况（左偏链）： $h = n$ ，栈深 $O (n)$ 。

题面声明 $n \leq 1000$ ，定长 stack[1024] 已留余量；若 $n_{max}$ 放大需相应改写为动态数组或带头指针的链式栈。

与递归实现对比：递归的系统调用栈深也是 $O (h)$ ——它本质上就是 LLVM/编译器自动管理的"显式栈"。空间复杂度量级一致；常数因子上递归每帧含返回地址、寄存器保存等额外开销，非递归仅存一个指针，常数更小。

易错点

本题不在"想不到用栈"——而在于栈状态的边界条件和递归到非递归的语义对齐。考研阅卷里非递归中序的典型扣分集中在下面 5 类。

盲区 A：「队列代栈」（思路层错路）
考生看到"遍历二叉树"会本能搬层序遍历的队列模板，写出：
c
```
Queue Q;  enqueue(Q, T);
while (!empty(Q)) {
    p = dequeue(Q);
    if (p->lchild) enqueue(Q, p->lchild);
    out[cnt++] = p->data;          // 错！这是层序，不是中序
    if (p->rchild) enqueue(Q, p->rchild);
}
```
错误推演：队列是 FIFO，对二叉树 1(2(4, 5), 3) 输出会得到层序 1 2 3 4 5，而中序应是 4 2 5 1 3。完全偏离中序定义。
正解：中序必须用栈不是队列——因为中序的访问次序"左 → 根 → 右"要求"先到的祖先后被访问"，这正是 LIFO（后入先出）语义。本盲区命名为「容器选错」，在 [[preorder]] / [[postorder]] / [[level-order]] 三种遍历的非递归实现里都要主动回扣：前/中/后序用栈，层序用队列。
盲区 B：「沿左链走到底没写成 while」（最高频实现错）
考生写：
c
```
while (p != NULL || top >= 0) {
    if (p != NULL) {               // 错！应该用 while
        stack[++top] = p;
        p = p->lchild;
    } else {
        p = stack[top--];
        out[cnt++] = p->data;
        p = p->rchild;
    }
}
```
错误推演：用 if 替代内层 while 会让程序在"入栈一次后立即重新评估外层循环条件"，导致沿左链每下一步都要绕一圈外层判断。逻辑上看似无害，但若有人进一步把 if 与 else 写错优先级（如不小心写成 if-else 反序），程序行为完全错乱。更严重的版本：
c
```
while (p != NULL || top >= 0) {
    stack[++top] = p;              // 错！没判 p 非空就入栈
    p = p->lchild;
    if (p == NULL) {
        p = stack[top--];
        out[cnt++] = p->data;
        p = p->rchild;
    }
}
```
这种写法会把"p == NULL 这件事"在栈顶留下空指针，下次弹出后解引用 out[cnt++] = NULL->data 直接 segfault。
正解：标准模板内层必须用 while (p != NULL) 把"沿左链入栈"走到底；只有走到 NULL 才出栈访问。本盲区命名为「沿左链没走透」。
盲区 C：「外层循环条件少写一项」
考生写：
c
```
while (top >= 0) {                 // 错！漏了 p != NULL
    while (p != NULL) { ... }
    p = stack[top--];
    ...
}
```
或：
c
```
while (p != NULL) {                // 错！漏了 top >= 0
    while (p != NULL) { ... }
    p = stack[top--];
    ...
}
```
错误推演：
- 第一种（只看栈）：进入时 p = T 非空但栈空，外层 top >= 0 不成立——整个循环不进入，输出空序列。
- 第二种（只看 p）：刚弹完一个节点、p 指向其右子树而右子树为空时 p == NULL，但栈里可能还压着更上层的祖先——此时循环退出，丢失上层未访问的节点。
正解：两个条件必须用 || 连接缺一不可。"p 非空"表示还有未走完的左链，"栈非空"表示还有待回溯访问的祖先——只要任一成立就要继续。本盲区与 [[singly-linked-list]] 类题"遍历用 while (p != NULL) 还是 while (p->next != NULL)"同源——都是"循环何时停"的边界判定。
盲区 D：「访问与转右顺序颠倒」（语义层错位）
考生写：
c
```
p = stack[top--];
p = p->rchild;                     // 错！先转右
out[cnt++] = p->data;              // 此时 p 已经是右子节点，不是要访问的节点
```
或
c
```
p = stack[top--];
out[cnt++] = p->rchild->data;      // 错！直接输出右孩子值
```
错误推演：弹栈得到的指针就是中序应输出的节点本身——这是非递归中序整个模板的核心承诺。错写成"先转右再输出"会把"应输出的节点"和"它的右子节点"混为一谈：例如二叉树 1(2, 3)，期望中序 2 1 3，错解会先弹出 2、转向 2.rchild = NULL、然后试图解引用 NULL 产生段错误；即使加了空指针保护跳过这一步，下一轮也已经丢失了对节点 2 的访问。
正解：「弹栈 → 立即输出 → 再转右」三件事的次序绝不可换。可以理解为"栈顶就是中序待访问者，访问它时手里掌握着所有还没访问的祖先和右子树入口；转右是给下一轮做准备"。本盲区命名为「弹栈即访问」，记住"出栈瞬间是访问的瞬间"。
盲区 E：「栈容量没声明够 / 用了 std::stack 之类的 STL」（元层 / 工程素养）
考生在非递归中序里写：
c
```
BiTNode *stack[100];               // 错！n 可达 1000，左偏链时栈深 = n
```
或在 408 答卷里写：
c
```
stack<BiTNode*> s;                 // 错！408 大题约定用 C 语言 + 自定义结构
```
错误推演：
- 容量不够：左偏链 $n = 1000$ 时栈深需 1000，声明 100 在 case 04（左偏链）上立刻数组越界——结果可能是任意垃圾值（更糟的是覆写了相邻局部变量），表现为随机 WA，难以 debug。
- STL：408 大纲明确以 C 语言为基线，答卷里用 C++ STL 既不符合考查目标，也可能被扣分。同理"非递归"题目里调用系统函数封装的递归（如 std::for_each、自定义递归 helper）同样属于绕开考点。
正解：自己声明定长 / 动态指针数组，容量至少为题面声明的 $n_{max}$ （加少量余量），如 BiTNode *stack[1024];。这是元层认知盲区——算法逻辑会写但"声明容量"这步常被一笔带过。本盲区命名为「栈深没算明白」，与 [[stack-application]] 题"卡特兰数估计栈深"是同源——任何用栈的题都要先估容量。

完成清单

11 道选择题均已独立作答，错题能说明其余选项为何不成立；
3 道综合题均已独立完成，并在展开解析前写出推导或算法；
能把本组题目涉及的关键性质、遍历顺序或算法复杂度说清楚；
已记录仍需回到教材复习的知识点。

复盘

哪道题最容易因遍历顺序、层次口径或结构关系判断失误？
我能否不用背答案，重新画树或写出访问过程？
如果题目改变一个条件，原结论是否仍成立？

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

目标 ​

前置知识 ​

环境、输入与预期输出 ​

作答方法 ​

选择题 ​

综合题 ​

综合题 1｜2017 年真题第 41 题 ​

(1) 设计思想 ​

(2) 代码实现 ​

综合题 2｜2022 年真题第 41 题 ​

(1) 设计思想 ​

(2) 代码实现 ​

综合题 3｜巩固题 ​

思路分析 ​

解法 1（朴素错路）：层序遍历过程中按位置分类 ​

解法 2（最优）：显式栈，沿左链入栈、出栈访问、转右子树 ​

与递归的等价性论证 ​

参考实现（C） ​

例：在具体二叉树上 trace 非递归过程 ​

复杂度证明 ​

易错点 ​

完成清单 ​

复盘 ​

目标

前置知识

环境、输入与预期输出

作答方法

选择题

综合题

综合题 1｜2017 年真题第 41 题

(1) 设计思想

(2) 代码实现

综合题 2｜2022 年真题第 41 题

(1) 设计思想

(2) 代码实现

综合题 3｜巩固题

思路分析

解法 1（朴素错路）：层序遍历过程中按位置分类

解法 2（最优）：显式栈，沿左链入栈、出栈访问、转右子树

与递归的等价性论证

参考实现（C）

例：在具体二叉树上 trace 非递归过程

复杂度证明

易错点

完成清单

复盘