中序遍历

概述

中序遍历（Inorder Tree Walk） 是二叉树的三种经典深度优先遍历之一，按照”左子树 → 根节点 → 右子树”的顺序访问每个节点。对于二叉搜索树，中序遍历的输出恰好是 key 的单调递增序列，这是 BST 最核心的性质之一（定理12.1）。

定义

中序遍历

中序遍历是一棵二叉树的遍历方式，按照以下递归顺序访问节点：

1. 递归遍历左子树
2. 访问根节点
3. 递归遍历右子树

伪代码

CLRS 给出的 INORDER-TREE-WALK 过程：

INORDER-TREE-WALK(x)
1  if x ≠ NIL
2      INORDER-TREE-WALK(x.left)
3      print x.key
4      INORDER-TREE-WALK(x.right)

逐步执行示例

对以下 BST 执行中序遍历：

        6
       / \
      2   8
     / \   \
    1   4   9
       / \
      3   5

调用栈展开过程：

步骤	操作	输出
1	调用 INORDER-TREE-WALK(6)
2	→ 递归左子树 INORDER-TREE-WALK(2)
3	→ → 递归左子树 INORDER-TREE-WALK(1)
4	→ → → 1 无左子树，打印 1	1
5	→ → → 1 无右子树，返回
6	→ → 打印 2	1, 2
7	→ → 递归右子树 INORDER-TREE-WALK(4)
8	→ → → 递归左子树 INORDER-TREE-WALK(3)
9	→ → → → 3 无左子树，打印 3	1, 2, 3
10	→ → → → 3 无右子树，返回
11	→ → → 打印 4	1, 2, 3, 4
12	→ → → 递归右子树 INORDER-TREE-WALK(5)
13	→ → → → 5 无左子树，打印 5	1, 2, 3, 4, 5
14	→ → → → 5 无右子树，返回
15	打印 6	1, 2, 3, 4, 5, 6
16	递归右子树 INORDER-TREE-WALK(8)
17	→ → 8 无左子树，打印 8	1, 2, 3, 4, 5, 6, 8
18	→ → 递归右子树 INORDER-TREE-WALK(9)
19	→ → → 9 无左子树，打印 9	1, 2, 3, 4, 5, 6, 8, 9
20	→ → → 9 无右子树，返回

最终输出：1 2 3 4 5 6 8 9 — 单调递增序列。

核心性质

BST 中序遍历输出有序序列

定理12.1

若对二叉搜索树进行中序遍历，输出的 key 序列是单调递增的。

证明思路（完整证明见 二叉搜索树）：

对任意节点 $x$，中序遍历先输出左子树 $L$（所有 key $\le x.key$），再输出 $x.key$，最后输出右子树 $R$（所有 key $\ge x.key$）。由归纳法可得完整序列递增。

时间复杂度

时间复杂度： $\Theta (n)$

中序遍历访问树中的每个节点恰好一次，每个节点的处理时间为 $\Theta (1)$（一次比较 + 一次打印），因此总时间为 $\Theta (n)$，其中 $n$ 为树中节点数。

分析：设 $T(n)$ 为遍历 $n$ 个节点的子树所需时间，则： $T(n)=T(k)+\Theta (1)+T(n-1-k)$ 其中 $k$ 为左子树的节点数。由主定理（或直接观察每节点恰好访问一次），$T(n)=\Theta (n)$。

三种遍历方式对比

遍历方式	访问顺序	BST 上的特殊性质
中序遍历	左 → 根 → 右	输出递增有序序列
先序遍历	根 → 左 → 右	输出树的”前缀表示”
后序遍历	左 → 右 → 根	用于释放子树空间

章节扩展

中序遍历是 BST 的基础操作，为以下操作提供理论支撑：

• TREE-SEARCH：搜索过程本质上是在中序序列中做二分查找的树形模拟
• TREE-INSERT：插入后 BST 性质不变，因此中序遍历仍输出有序序列
• TRANSPLANT：替换子树后若保持 BST 性质，中序遍历结果仍然有序

参见

• 二叉搜索树 — BST 的完整定义与性质
• TREE-SEARCH — 在 BST 中查找关键字
• TREE-INSERT — 向 BST 插入新节点
• 散列表 — 不支持有序遍历的动态集合实现