Appearance
中序遍历
为什么需要中序遍历
二叉树的遍历是树结构最基本的操作，而中序遍历是三种深度优先遍历方式之一。它按照左子树 → 根结点 → 右子树的顺序访问所有结点。
中序遍历最重要的性质：对二叉排序树（BST） 进行中序遍历，得到的序列恰好是递增有序的。这一性质在 408 考研中反复出现，是判断 BST 合法性、求第 k 小元素等问题的核心思路。
核心思想
中序遍历的访问顺序：左子树 → 根结点 → 右子树（LNR）。
以下面的二叉树为例：
A
/ \
B C
/ \ \
D E F中序遍历序列为：D → B → E → A → C → F
递归过程展开：
- 先递归遍历 A 的左子树（以 B 为根）
- 再递归遍历 B 的左子树（以 D 为根）
- D 无左子树，访问 D；D 无右子树，返回
- 访问 B
- 递归遍历 B 的右子树，访问 E
- 左子树遍历完毕，访问 A（根结点）
- 递归遍历 A 的右子树（以 C 为根）
- C 无左子树，访问 C
- 递归遍历 C 的右子树，访问 F
中序遍历流程图
中序遍历的核心顺序：左 → 根 → 右。先递归处理左子树，再访问根结点，最后递归处理右子树。对 BST 进行中序遍历可得到递增有序序列。
交互可视化
通过下方的交互动画，你可以逐步观察中序遍历的执行过程：
操作详解
递归实现
递归实现思路非常直观，直接按照"左→根→右"的定义编写即可。
cpp
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void InOrder(BiTree T) {
if (T == NULL) return;
InOrder(T->lchild); // 递归遍历左子树
visit(T); // 访问根结点
InOrder(T->rchild); // 递归遍历右子树
}递归实现代码简洁，但每次调用都会在系统栈中压入一个栈帧。当树的深度很大时，可能导致栈溢出。
非递归实现（栈）
非递归实现的核心思路：用一个显式栈来模拟递归过程。
关键步骤：
- 从根结点出发，沿左子树一路入栈，直到左子树为空
- 栈顶元素出栈并访问
- 转向该结点的右子树，重复步骤 1
cpp
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; // 转向右子树
}
}
}以上述示例树为例，栈的变化过程：
| 步骤 | 操作 | 栈内容（底→顶） | 访问结点 |
|---|---|---|---|
| 1 | A 入栈，向左 | A | - |
| 2 | B 入栈，向左 | A, B | - |
| 3 | D 入栈，向左 | A, B, D | - |
| 4 | 左空，弹出 D | A, B | D |
| 5 | D 右空，弹出 B | A | B |
| 6 | 转向 B 的右子树，E 入栈 | A, E | - |
| 7 | E 左空，弹出 E | A | E |
| 8 | E 右空，弹出 A | （空） | A |
| 9 | 转向 A 的右子树，C 入栈 | C | - |
| 10 | C 左空，弹出 C | （空） | C |
| 11 | 转向 C 的右子树，F 入栈 | F | - |
| 12 | F 左空，弹出 F | （空） | F |
最终访问顺序：D → B → E → A → C → F，与递归结果一致。
复杂度分析
| 实现方式 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归 | O(n) | O(n) | 每个结点访问一次；栈深度最坏为 n（斜树） |
| 非递归（栈） | O(n) | O(n) | 每个结点入栈、出栈各一次；栈空间最坏为 n |
说明：n 为二叉树的结点总数。空间复杂度的最好情况为 O(log n)，出现在完全二叉树等平衡结构中。
考研高频考点
- ⭐ 对 BST 进行中序遍历可得到递增有序序列（选择题/判断题高频）
- ⭐ 根据中序 + 先序（或后序）序列还原二叉树（大题必考）
- ⭐ 中序遍历非递归算法的手写实现（算法题高频）
- ⭐ 给定二叉树画出中序遍历序列（基础送分题）
- 三种遍历的递归算法对比（仅 visit 位置不同）
- 中序遍历在线索二叉树中的应用（中序线索化）