中序遍历

2026 大纲 四（二）3 二叉树的遍历 · 中序部分，兼三种遍历共用的非递归统一模板（前序见《前序遍历》、后序见《后序遍历》、层序见《层序遍历》）。

中序：等左子树全处理完，才轮到根

左子树 → 根结点 → 右子树（LNR）。在遍历的固定游走路线上，每个结点被经过三次（见前序遍历的"三次经过"图），中序取第二次——左子树已经处理完、右子树还没开始的那一刻。

这个次序有个很好用的几何直观：把所有结点垂直投影到一条水平线上（保持左子树在左、右子树在右），从左往右读出来就是中序序列。

        A
       / \
      B   C
     / \   \
    D   E   F

投影到水平线：   D   B   E   A   C   F

这张图值得多看两眼，因为中序两个最重要的用途都能从它上面直接读出来："把树摊平成一条有序序列"，以及"某个结点的前驱后继在哪儿"——投影线上它左边那个就是前驱、右边那个就是后继。前者通向二叉排序树，后者通向线索二叉树。

先看一眼

加载可视化中...

看完你应该确认：一个结点被访问的时刻，是它的左子树刚走完、右子树还没进去的那一瞬间。

递归实现

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

void InOrder(BiTree T) {
    if (T == NULL) return;   // 递归出口
    InOrder(T->lchild);      // 先把左子树整个处理完
    visit(T);                // 访问根 —— visit 夹在两次递归之间，这就是"中序"
    InOrder(T->rchild);      // 再处理右子树
}

跟着上面那棵树走一遍：先递归 A 的左子树（根 B）→ 再递归 B 的左子树（根 D）→ D 无左子树，访问 D，D 无右子树，返回 → 访问 B → 递归 B 的右子树，访问 E → A 的左子树完毕，访问 A → 递归 A 的右子树（根 C），C 无左子树，访问 C → 递归 C 的右子树，访问 F。得到 D B E A C F，与投影线一致。

递归写法简洁，但栈帧由系统分配、深度不可控，树退化时可能栈溢出。下面的非递归实现把这个栈显式地拿到手里。

中序最要紧的一条：BST 的中序序列递增

二叉排序树（BST）的定义是：左子树所有结点的值 $<$ 根 $<$ 右子树所有结点的值，且左右子树也是 BST。把它和中序的访问次序（先左、再根、后右）摆在一起，结论立刻出来：

对 BST 做中序遍历，得到的一定是严格递增的有序序列。

证明只要对结点数归纳一句：空树与单结点显然成立；设左右子树的中序序列各自递增，则整棵树的中序序列是「左子树序列，根，右子树序列」的拼接，而由 BST 的定义左子树全部 $<$ 根 $<$ 右子树全部，三段拼起来仍然递增。

逆命题同样要紧：中序序列不递增，就一定不是 BST。这是判定 BST 唯一可靠的方法。 很多人想当然地写成"逐个结点检查它比左孩子大、比右孩子小"，那是错的：

      5
     / \
    3   8
       / \
      2   9      ← 8 > 5、2 < 8、9 > 8，逐点检查全过

中序序列是 3 5 2 8 9（ $5 > 2$ ，不递增），所以不是 BST。问题出在结点 2：它是 8 的左孩子（局部合法），却落在根 5 的右子树里（全局非法）。局部检查漏掉跨层违规，中序检查不会。

由这一条还能顺出三个直接可用的结论：

BST 中序序列的第 $k$ 个元素就是第 $k$ 小的关键字——中序序列即升序序列；
同一关键字集合、不同插入次序建出的 BST 形态不同，但中序序列完全相同——中序序列就是该集合的升序排列，与形态无关；
BST 的前序序列可以单独确定这棵 BST——把前序排个序就得到中序，于是等价于"前序 + 中序"。

非递归实现：三种遍历共用的统一模板

把递归占用的系统栈换成自己的栈：沿左链一路下潜、逐层压栈，潜到空指针就回退一层，访问它，再转去它的右子树。

void InOrder_NonRecursive(BiTree T) {
    Stack S;
    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;     // 转向右子树，重复"一路向左"
        }
    }
}

这十行代码的循环不变量是：栈中自底向上存放的，恰好是当前子树的所有祖先中"左子树已处理完、根未访问、右子树未处理"的那些结点——换句话说，是一条从根出发、还欠着"访问自己 + 处理右子树"的路径。三个动作各自的道理：

Push(S, p); p = p->lchild; —— 记账后下潜。中序要求左子树先于根，所以见到结点先欠着，往左走。
Pop(S, p); visit(p); —— 还账。能弹出说明它的左子树已经全部走完，轮到它了。
p = p->rchild; —— 转右。根访问完了，最后一步是右子树，且此后再不需要这个结点，所以它已经出栈。

循环条件为什么必须写成"或"，两边各管一件事：

只写栈非空：初始时栈是空的（根还没入栈），循环根本不会开始；而且每次转向右子树后若栈恰好空了，那棵右子树会被整个丢掉。
只写 p != NULL：p 走到最左端变成 NULL 时循环就结束了，栈里那一串祖先永远不会被访问。

模板的逐步执行表（想亲手跟一遍就展开）

以上文那棵树为例：

步骤	操作	栈内容（底→顶）	访问结点
1	A 入栈，向左	A	—
2	B 入栈，向左	A, B	—
3	D 入栈，向左	A, B, D	—
4	p 空，弹出 D 并访问	A, B	D
5	转向 D 的右子树（空），弹出 B 并访问	A	B
6	转向 B 的右子树，E 入栈，向左	A, E	—
7	p 空，弹出 E 并访问	A	E
8	转向 E 的右子树（空），弹出 A 并访问	（空）	A
9	转向 A 的右子树，C 入栈，向左	C	—
10	p 空，弹出 C 并访问	（空）	C
11	转向 C 的右子树，F 入栈，向左	F	—
12	p 空，弹出 F 并访问	（空）	F

最终访问顺序 D → B → E → A → C → F，与递归结果一致。栈里存的始终是"当前结点到根的路径"，所以最大深度恰为树高 $h$ 。

空间是 $O (h)$ 而不是 $O (n)$ ，原因就在不变量里：栈里装的是一条路径，不是一层结点。 时间恒为 $O (n)$ ——每个结点恰好入栈一次、出栈一次、访问一次；"一路向左"看着像嵌套循环，但所有内层步数加起来正好等于入栈总次数 $n$ 。

前序由它一行改出来，后序改不出来

派生前序：只需把 visit 从"出栈时"提前到"入栈前"。前序要求根在左右子树之前，而入栈那一刻正是第一次见到这个结点。

if (p != NULL) {
    visit(p);          // ← 唯一改动：提前到这里
    Push(S, p);
    p = p->lchild;
} else {
    Pop(S, p);
    p = p->rchild;
}

后序改不动。 模板里结点只被弹出一次，而弹出的那一刻分不清两种情况："刚从左子树回来、右子树还没去"和"右子树也回来了、可以访问了"——这两种状态在栈上长得一模一样。

所以"后序非递归最难"的准确原因不是代码长，而是模板缺一个状态位。补法只有两条：记住上一个被访问的结点（标记法，用 r 指针判断右子树是否刚被访问完），或者换个角度绕开（双栈法，先做 NRL 再整体逆序）。完整推导见后序遍历。理解了"缺一个状态位"这一层，那两种写法就都是自然产物，不必死记。

遍历	访问时机	需不需要额外状态
前序	入栈前（第一次见到）	不需要
中序	出栈时（左子树已完）	不需要
后序	出栈时且右子树已完	需要：`r` 指针（标记法）或第二个栈（双栈法）

中序驱动的任务

1. 判定一棵二叉树是不是 BST。 做一次中序遍历，检查序列是否严格递增。不必真存下整个序列，只需记住上一个访问的值：

int pre = INT_MIN;        // 上一个中序访问到的关键字
int ok = 1;

void CheckBST(BiTree T) {
    if (T == NULL || !ok) return;
    CheckBST(T->lchild);
    if (T->data <= pre) ok = 0;   // 中序序列必须严格递增
    pre = T->data;                // 更新"上一个"
    CheckBST(T->rchild);
}

边界注意：pre 的初值不能用 0（关键字可能是负数），也不能只在根处初始化一次却在多次调用间残留。若关键字可以取到类型最小值，改用"是否已访问过第一个结点"的布尔标志更稳妥。

这个骨架是代码大题的标准答案形态，换成顺序存储也只是把 T->lchild、T->rchild 换成下标 $2 i + 1$ 、 $2 i + 2$ ，把"指针为空"换成"下标越界或值为 $- 1$ "。

2. 求 BST 中第 $k$ 小的关键字。 中序遍历到第 $k$ 个访问的结点就是答案，遍历中计数、计满立即返回，平均只需走 $O (h + k)$ 步。

3. 中序线索化。 线索化的实质是"在遍历过程中把空指针改成指向前驱／后继的线索"。中序是首选次序，因为中序线索树上找前驱和后继都简单（前驱是左子树最右下、后继是右子树最左下），而前序线索找前驱、后序线索找后继都需要双亲信息。见线索二叉树。

4. 输出中缀表达式——但会丢括号。 对表达式树做中序遍历得到中缀式，问题是 $(a + b) \times c$ 与 $a + b \times c$ 的表达式树完全不同，中序序列却都是 a+b*c。要恢复正确的运算次序，必须在遍历时按子树补括号。 这正是中缀式需要括号、而前缀式与后缀式不需要的根本原因。

考点速记

三条会被反复调用的结论：

BST 的中序序列严格递增：既是判定 BST 唯一可靠的方法，也是"求第 $k$ 小"与中序线索化的基础。
三种遍历非递归共用一套栈框架：前序与中序只差 visit 的位置，后序必须额外记住"上次访问的结点"。
空间 $O (h)$ 的来历：栈里装的是一条从根到当前结点的路径，不是一层结点。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

中序序列里的位置关系。 两道题都建立在同一条性质上——中序前驱是"左子树中一路向右到底"的结点（必然没有右孩子），中序后继是"右子树中一路向左到底"的结点（必然没有左孩子）。一道问中序相邻的 $p$ 、 $q$ 之间哪种关系不可能，答案是右兄弟（两人分处共同双亲的左右子树，中间必夹着双亲）；一道给中序 $\dots p, v, q \dots$ 且 $v$ 有两个孩子，问 $p$ 、 $q$ 的孩子情况，答 $p$ 无右孩子、 $q$ 无左孩子。
判定 BST 的代码大题。 给顺序存储的二叉树判断是否满足 BST 定义，标准解法就是中序遍历 + 维护 prev，一旦当前值 $\leq$ prev 立即判否。顺序存储下左右孩子是 $2 i + 1$ 、 $2 i + 2$ ，越界或值为 $- 1$ 视为空子树直接返回。
表达式树输出中缀式的代码大题。 中序遍历的直接应用，考点正是必须补括号：递归到非叶结点时先输出 (、中序输出左子树与运算符与右子树、再输出 )。丢了括号运算次序就错了。
给树形 + 序列，反推是哪种遍历方式。 选项会给 LRN、NRL、RLN、RNL 这类"先左后右"之外的次序，做法是逐个选项在树上实跑一遍比对，别凭感觉。判别的抓手是序列首尾：首元素若是最右下的结点，多半是先走右子树的次序。
先序序列与中序序列相同的条件。 答案是所有非叶结点都只有右子树——先序"根左右"与中序"左根右"的差异全在"根"与"左"的相对位置，要让两者逐位相同只能让"左"消失。

易错：用"每个结点比左孩子大、比右孩子小"判定 BST。 这漏掉跨层违规，必须查中序序列是否递增。

易错：非递归的循环条件只写一半。 只判栈非空则循环压根不启动，只判 p != NULL 则栈里的祖先永远不被访问。

易错：以为后序也能靠改 visit 位置从模板派生。 弹栈时两种状态无法区分，必须补状态位。

易错：表达式树中序输出时不补括号。 $(a + b) \times c$ 与 $a + b \times c$ 的中序序列相同。

教材出处

遍历二叉树的定义与三种遍历的操作定义（"若二叉树为空则空操作，否则……"）：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p122（5.5.1 节）
中序遍历的递归算法（算法 5.1），以及"只要改变输出语句的顺序便可类似实现先序和后序""三种遍历算法不同处仅在于访问根结点和遍历左右子树的先后关系"：印刷 p123
中序遍历的非递归算法（算法 5.2）及其算法步骤"如果 $p$ 非空则将 $p$ 进栈、 $p$ 指向该结点的左孩子；如果 $p$ 为空则弹出栈顶元素并访问、将 $p$ 指向该结点的右孩子"：印刷 p124
遍历的复杂度分析（时间 $O (n)$ ；辅助空间为栈的最大容量即树的深度，最坏 $O (n)$ ）：印刷 p125
二叉排序树的定义及"中序遍历一棵二叉排序树时可以得到一个结点值递增的有序序列"：印刷 p198（7.3.1 节）

真题练习

2024Q32分 2022Q32分 2022Q4113分 2017Q42分 2017Q4115分

中序遍历

中序：等左子树全处理完，才轮到根

先看一眼

递归实现

中序最要紧的一条：BST 的中序序列递增

非递归实现：三种遍历共用的统一模板

前序由它一行改出来，后序改不出来

中序驱动的任务

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（5题）

中序遍历 ​

中序：等左子树全处理完，才轮到根 ​

先看一眼 ​

递归实现 ​

中序最要紧的一条：BST 的中序序列递增 ​

非递归实现：三种遍历共用的统一模板 ​

前序由它一行改出来，后序改不出来 ​

中序驱动的任务 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（5题）

中序遍历

中序：等左子树全处理完，才轮到根

先看一眼

递归实现

中序最要紧的一条：BST 的中序序列递增

非递归实现：三种遍历共用的统一模板

前序由它一行改出来，后序改不出来

中序驱动的任务

考点速记

相关知识

真题练习