树的遍历（先序、中序、后序） - 六级

二叉树的三种遍历：先序、中序、后序（深度优先）

遍历，就是把树里的每个节点都“拜访”一次，就像老师按名单点名，一个都不能少。对于二叉树，有三种经典的“点名”顺序：先序、中序、后序。它们都采用“深度优先”的思想——先一头扎到树的最深处，再一层层往回走。

我们可以把递归遍历想象成玩“走迷宫”：每次遇到岔路口（节点），你决定先去左边看看，还是右边，还是先记下当前位置。不同的决定顺序，就形成了不同的遍历序列。

1. 三种遍历的规则

假设树长这样（每个字母代表一个节点）：

    A
   / \
  B   C
 / \
D   E

先序遍历（Pre-order）：根 → 左 → 右
先访问根节点，然后遍历左子树，最后遍历右子树。
生活例子：整理书架时，你先把一本书放在桌上（根），然后从左到右把同一排的其他书摆好。
结果：A, B, D, E, C
中序遍历（In-order）：左 → 根 → 右
先遍历左子树，然后访问根节点，最后遍历右子树。
生活例子：按学号从小到大点名——先点小号（左边），再点中间，最后点大号（右边）。对于二叉搜索树，中序得到升序序列。
结果：D, B, E, A, C
后序遍历（Post-order）：左 → 右 → 根
先遍历左子树，然后遍历右子树，最后访问根节点。
生活例子：吃完一顿套餐，先吃配菜（左右），最后才吃主食（根）。在删除树时，需要先删除子节点再删根节点。
结果：D, E, B, C, A

注意：三种顺序产生的序列完全不同。什么时候用哪种？

先序：适合复制一棵树（先复制根，再复制左右子树）。
中序：适合对二叉搜索树排序（从小到大输出）。
后序：适合删除整棵树（先删孩子，再删爹妈）。

2. 递归背后的魔法：调用栈

递归为什么能“自然地”完成深度优先遍历？因为函数调用自己时，计算机会在内存里维护一个“调用栈”。每进入下一层，就把当前节点的信息压入栈；返回时自动弹出，继续执行上层代码。

打个比方：你走进一栋大楼的楼梯间（根节点），先去左边的房间（左子树）巡查，每个房间又分好多小房间。你一层层往里走，直到最深处的小房间（叶子节点），然后原路返回，每回到一层就继续检查右边的房间。整个过程中，“你应该去哪”的信息都记在脑子里（就是递归栈）。

3. C++ 代码实现（带详细注释）

下面代码使用链表结构表示二叉树，并实现三种遍历。变量名使用简短英文单词，每行变量定义都加了中文注释。

#include <iostream>
using namespace std;

// 定义树节点结构
struct Node {
    char data;          // 节点数据（这里用字符，比如 'A'）
    Node* left;         // 左孩子指针
    Node* right;        // 右孩子指针
};

// 创建新节点，参数 val 是要存入的字符
Node* createNode(char val) {
    Node* n = new Node;     // 申请一块内存
    n->data = val;           // 存入数据
    n->left = n->right = nullptr;  // 左右孩子初始为空
    return n;
}

// 先序遍历（根左右）
void preOrder(Node* node) {
    if (node == nullptr) return;    // 如果当前节点为空，返回
    cout << node->data << " ";      // 1. 访问根节点
    preOrder(node->left);           // 2. 递归遍历左子树
    preOrder(node->right);          // 3. 递归遍历右子树
}

// 中序遍历（左根右）
void inOrder(Node* node) {
    if (node == nullptr) return;
    inOrder(node->left);            // 1. 递归遍历左子树
    cout << node->data << " ";      // 2. 访问根节点
    inOrder(node->right);           // 3. 递归遍历右子树
}

// 后序遍历（左右根）
void postOrder(Node* node) {
    if (node == nullptr) return;
    postOrder(node->left);          // 1. 递归遍历左子树
    postOrder(node->right);         // 2. 递归遍历右子树
    cout << node->data << " ";      // 3. 访问根节点
}

int main() {
    // 手动构建这棵树：
    //        A
    //      /   \
    //     B     C
    //   /   \
    //  D     E
    Node* root = createNode('A');      // 根节点 A
    root->left = createNode('B');      // A 的左孩子 B
    root->right = createNode('C');     // A 的右孩子 C
    root->left->left = createNode('D');   // B 的左孩子 D
    root->left->right = createNode('E');  // B 的右孩子 E

    cout << "先序遍历: ";
    preOrder(root);
    cout << endl;

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

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

    // 注意：程序结束时没有释放内存，但在简单示例中可忽略。
    return 0;
}

运行结果：

先序遍历: A B D E C
中序遍历: D B E A C
后序遍历: D E B C A

与前面手算的结果完全一致。

4. 新手最容易犯的三个错误

忘记写递归终止条件
if (node == nullptr) return; 是必须的，否则递归会无限循环，导致栈溢出。比如遍历到叶子节点的左右孩子时，它们都是 nullptr，如果没判断，程序会尝试访问 node->data 而崩溃。
左右子树顺序搞反
- 先序：先左后右，写成先右后左？会得到镜像序列。
- 中序：左、根、右，如果写成根、左、右，那就变成了先序。
- 后序：左、右、根，如果写成右、左、根，就变成了逆后序。
  建议先在纸上画一棵小树，用手模拟递归过程，确认顺序。
用全局变量时忘记重置
如果遍历时使用了全局容器（比如 vector<int> result）存储结果，多次调用遍历前要清空，否则上次的结果会混在一起。不过上面代码直接打印，不存在此问题。

5. 完整示例：自己搭建一棵树试试

你可以修改 main 函数中树的形状，比如再增加一个右子树的分支，看看输出变化。例如改成下面这样（更复杂的树）：

只需要添加一行 root->right->right = createNode('F');，再运行程序，你就会看到三种序列各自的结果。建议亲手试一下，体会递归是如何深入到每个角落的。

6. 学完这个，接下来可以学什么？

层序遍历（广度优先）：按层从上到下、从左到右依次访问，需要借助队列实现。
二叉搜索树：利用中序遍历的有序性，可以快速查找、插入、删除。
非递归遍历：用栈模拟递归，锻炼对栈的理解，也是面试常考内容。
根据遍历序列重建二叉树：比如已知先序和中序，如何唯一确定一棵树？这是经典算法题。

三种遍历是二叉树最基础的操作，掌握后很多进阶算法（如表达式树、哈夫曼树）都会轻松很多。多画图、手写递归过程，你会很快爱上这种“聪明”的递归方式。