二叉树中序遍历（Inorder Traversal）

算法原理

中序遍历的口诀是**「左根右」：先递归遍历左子树，返回时才记录当前根，最后递归遍历右子树。和先序"进入即记"相反，中序是从左子树回来才记**——节点必须等左边的所有事都了结，才轮到它出场。

本动画用同一棵 7 节点的完全二叉搜索树演示（默认 2s/拍，全片 22 拍）：

树：根 5（左子 3，右子 8）；3 的孩子 1、4；8 的孩子 7、9
中序输出：1 3 4 5 7 8 9
节拍：宣告 1 + 进入 7 + 访问 7 + 返回 6 + 完成 1

最大的看点是输出恰好是升序：这棵树是二叉搜索树（左 < 根 < 右），中序遍历把"左小根中右大"的局部性质拼接成全局有序序列——1 3 4 5 7 8 9。这是 BST 最著名的性质：中序 = 排序。

动画怎么看

• 上半区是树：7 个节点盒 + 父子实线连线；黄色描边 = 遍历者焦点，逐拍移动，本拍移动的边青色加粗；访问过的节点转绿色常驻；
• 进入拍：焦点落到新节点，状态行显示 进入 v · 暂不记录——输出条不动，这是中序和先序最直观的区别；
• 访问拍：从左子树返回的那一拍，输出条才写入该节点的值，节点转绿；
• 口诀立牌：左上角常驻「口诀 左根右」——看每一拍都问自己：左边完了吗？完了才记它；
• 大✓：✓ 完成 ｜ 中序遍历 7 节点全部输出，7 格正好从小到大。

复杂度分析

C++ 参考代码

#include <iostream>
struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);             // 左：左子树全部了结
    std::cout << root->val << " ";   // 根：返回时才记录
    inorder(root->right);            // 右：最后右子树
}

int main() {
    // 完全 BST：5(3(1,4), 8(7,9))
    Node a(1), b(4), c(3), d(7), e(9), f(8), root(5);
    c.left = &a; c.right = &b;
    f.left = &d; f.right = &e;
    root.left = &c; root.right = &f;
    inorder(&root);                  // 输出 1 3 4 5 7 8 9（升序）
    return 0;
}

什么时候用中序遍历

中序的招牌场景全部围着 BST 转：中序求第 k 小（在升序序列里数到第 k 个即是）、验证一棵树是不是 BST（中序严格递增即可）、中序后继 / 前驱查询；表达式树上中序还原中缀式（必要时补括号）。更实用的一句心法：看到 BST 想中序——凡是要"按大小顺序"处理 BST 节点的题，中序一上来序列就有序了。动画里"进入不记、回来才记"的那一停一顿，就是中序区别于其他遍历的全部秘密。