二叉树遍历：前序、中序、后序——像逛博物馆一样走遍每个节点

遍历是什么意思？

想象你第一次去逛一座大博物馆，里面有很多展厅，每个展厅又分成若干小隔间。如果你想一个不落地看完所有展品，就得计划一条路线，按顺序走一遍。二叉树的遍历就是做同样的事：按照某种规定的顺序，访问树中的每一个节点恰好一次。

为什么需要遍历呢？因为树形结构不像数组或链表那样有天然的顺序，我们要检查节点的值、搜索某个数据、或者打印所有信息，都必须先把所有节点“走一遍”。最常见的三种走法就是前序、中序和后序，它们的区别在于“什么时候访问根节点”。

三种遍历的规则

前序遍历（根左右）

规则：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

形象记忆：你走进一个房间，先看房间中间的主人（根），再去看左边房间（左子树），最后看右边房间（右子树）。
生活中的例子：整理书架时，你每看到一层书柜，先拿掉中间那本书（根），再整理左边格子（左子树），最后整理右边格子（右子树）。这样一层一层递归下去。
输出特点：根节点总是在它的左右子树之前出现，所以前序遍历常用来复制一棵树或输出树的整体结构。

中序遍历（左根右）

规则：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

形象记忆：你从左边的展区开始逛，逛完左边后回到中间主厅看展品，再逛右边的展区。
生活中的例子：排队买冰淇淋，你按照“左边队伍先买，然后轮到中间窗口，最后右边窗口”的顺序来叫号。
输出特点：对于二叉搜索树，中序遍历的结果是升序排列。因为左子树所有值 < 根 < 右子树所有值，所以中序遍历会输出从小到大的有序序列。

后序遍历（左右根）

规则：先递归地遍历左子树，再递归地遍历右子树，最后访问根节点。

形象记忆：先逛完所有偏厅（左右子树），最后才回到主厅看镇馆之宝（根）。
生活中的例子：你写作业，先做完数学（左子树）和语文（右子树），最后才做总结报告（根）。
输出特点：根节点最后才访问，所以后序遍历常用于删除整棵树——先删除子节点，最后才能安全地删除根节点，避免指针悬空。

用递归实现遍历——就像拆套娃

递归是遍历最自然的写法。想象一个大套娃，里面套着两个小套娃，每个小套娃又套着更小的……你要打开所有套娃，必须按顺序操作。

递归函数的核心就是：如果当前节点是空的，就返回；否则按规则顺序做三件事：访问当前节点、递归左子树、递归右子树。顺序不同，就得到不同的遍历。

下面我们用代码实现一个简单的二叉树，并演示三种遍历。

#include <iostream>
using namespace std;

// 定义树的节点结构
struct TreeNode {
    int val;              // 节点值
    TreeNode* left;       // 左子节点指针
    TreeNode* right;      // 右子节点指针
    // 构造函数：初始化节点值，左右子节点设为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历：根左右
void preorder(TreeNode* root) {
    if (root == nullptr) return;       // 空节点就返回
    cout << root->val << " ";          // 访问根
    preorder(root->left);              // 递归左子树
    preorder(root->right);             // 递归右子树
}

// 中序遍历：左根右
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);               // 递归左子树
    cout << root->val << " ";          // 访问根
    inorder(root->right);              // 递归右子树
}

// 后序遍历：左右根
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);             // 递归左子树
    postorder(root->right);            // 递归右子树
    cout << root->val << " ";          // 访问根
}

int main() {
    // 构建一棵小树
    TreeNode* root = new TreeNode(1);   // 根节点值为1
    root->left = new TreeNode(2);       // 左子节点值为2
    root->right = new TreeNode(3);      // 右子节点值为3
    root->left->left = new TreeNode(4); // 2的左子节点值为4
    root->left->right = new TreeNode(5);// 2的右子节点值为5
    // 树的结构：
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5

    cout << "前序遍历: ";
    preorder(root);
    cout << endl;

    cout << "中序遍历: ";
    inorder(root);
    cout << endl;

    cout << "后序遍历: ";
    postorder(root);
    cout << endl;

    // 记得释放内存（动态分配）——这里略写，实际项目要删除
    return 0;
}

运行结果：

前序遍历: 1 2 4 5 3
中序遍历: 4 2 5 1 3
后序遍历: 4 5 2 3 1

你可以对照上面的树结构手动画一画：

前序：先拿1，然后去左子树（以2为根），在2的子树里又先拿2，再拿4，再拿5，最后回到右子树拿3 → 1 2 4 5 3
中序：先遍历左子树到底：4，然后回到2，接着遍历5，然后回到1，然后遍历右子树3 → 4 2 5 1 3
后序：先遍历左子树，但根最后访问，所以左子树的4、5、2，然后右子树的3，最后根1 → 4 5 2 3 1

看到规律了吗？无论哪种顺序，每个子树的内部都遵循同样的规则。

新手常犯的四个错误

忘记递归终止条件

void inorder(TreeNode* root) {
    // 没有判断 root==nullptr，直接访问 root->val 会崩溃
    inorder(root->left);
    cout << root->val;
    inorder(root->right);
}

一定要加 if (root == nullptr) return; 作为递归出口，否则无限递归或访问空指针。

混淆三种顺序的代码位置
把 cout 放在递归调用之后，变成了后序；放在两个递归之间才是中序。初学者容易把前序写成根右左，或者少写一个递归调用。
对“左子树”理解不准确
root->left 是一棵子树，它本身可能还有子节点。不能只访问 root->left 这一个节点，而要用递归去遍历整个左子树。
忘记释放动态内存（C++）
用 new 创建的节点，最后要用 delete 释放，否则内存泄漏。虽然是简单示例，但养成好习惯很重要。实际编程中，常用智能指针或写一个 deleteTree 函数。

扩展：非递归的遍历（用栈模拟）

虽然递归很简洁，但递归过深可能导致栈溢出。实际竞赛中也会要求用栈实现非递归遍历。这里先简单提一下思路，你们可以后续深入学习：

前序非递归：用一个栈，先压入根，然后循环：弹出栈顶节点并访问，再依次压入它的右子、左子（因为栈是后进先出，所以先压右再压左，保证左先被访问）。
中序非递归：一直往左走，把节点压栈，直到空；然后弹出栈顶访问，再往右走，重复。
后序非递归：稍微复杂，可以用两个栈或用一个栈加一个标志。

记住：递归是思维利器，非递归是性能优化。作为初学者，先把递归练熟。

二叉树的遍历（前序、中序、后序）