4. 二叉树的遍历（上）：前序、中序、后序遍历（递归实现）

遍历二叉树，说白了就是按照某种规则，把树里的每个节点都访问一遍，而且不重复、不遗漏。这就像你走进一个迷宫，得有个策略才能确保每个房间都走到，不会迷路。

我个人习惯把遍历理解为“打印节点值的顺序”。你想想看，一棵二叉树长什么样？根节点在中间，左边挂着左子树，右边挂着右子树。那访问顺序的不同，就产生了三种经典的遍历方式：前序、中序、后序。

嗯，这里要注意，这三种遍历的名字，其实指的是“根节点”被访问的时机。

4.1 前序遍历（Preorder Traversal）

前序遍历的规则很简单：先访问根节点，再遍历左子树，最后遍历右子树。用一句话记就是“根左右”。

我在项目中遇到过这样一个场景：需要序列化一棵二叉树，把它存到文件里。当时我用的就是前序遍历。为什么？因为前序遍历的第一个节点就是根节点，反序列化的时候，拿到第一个值就能立刻创建根节点，非常方便。

来看代码实现：

// 前序遍历：根 -> 左 -> 右
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;  // 空树，直接返回
    }
    
    // 1. 访问根节点
    printf("%d ", root->data);
    
    // 2. 递归遍历左子树
    preorderTraversal(root->left);
    
    // 3. 递归遍历右子树
    preorderTraversal(root->right);
}

你看，代码非常简洁。递归的魅力就在这里——你不需要关心左子树里面还有多少层，递归会帮你搞定一切。

4.2 中序遍历（Inorder Traversal）

中序遍历的规则是：先遍历左子树，再访问根节点，最后遍历右子树。口诀是“左根右”。

中序遍历有一个非常重要的特性：对于二叉搜索树（BST），中序遍历的结果是递增有序的。我曾经用这个特性来验证一棵树是不是合法的二叉搜索树——只要中序遍历的结果是严格递增的，那就没问题。

代码实现如下：

// 中序遍历：左 -> 根 -> 右
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 1. 递归遍历左子树
    inorderTraversal(root->left);
    
    // 2. 访问根节点
    printf("%d ", root->data);
    
    // 3. 递归遍历右子树
    inorderTraversal(root->right);
}

你发现没有？前序和中序的代码几乎一模一样，唯一的区别就是 printf 的位置不同。前序放在最前面，中序放在中间。这就是递归遍历的规律——打印语句的位置决定了遍历顺序。

4.3 后序遍历（Postorder Traversal）

后序遍历的规则是：先遍历左子树，再遍历右子树，最后访问根节点。口诀是“左右根”。

后序遍历在实际开发中有一个经典用途：删除整棵树。你想啊，要删除一棵树，你得先把子节点都删掉，最后才能删根节点。这不就是后序遍历的思路吗？

代码实现：

// 后序遍历：左 -> 右 -> 根
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 1. 递归遍历左子树
    postorderTraversal(root->left);
    
    // 2. 递归遍历右子树
    postorderTraversal(root->right);
    
    // 3. 访问根节点
    printf("%d ", root->data);
}

后序遍历的代码，printf 放到了最后。你看，三种遍历的代码结构完全一样，就是 printf 的位置不同。这就是递归遍历的核心规律。

4.4 三种遍历的对比

为了让你看得更清楚，我把三种遍历放在一起对比：

遍历方式	访问顺序	口诀	典型应用
前序遍历	根 → 左 → 右	根左右	序列化二叉树、复制树
中序遍历	左 → 根 → 右	左根右	BST 排序输出
后序遍历	左 → 右 → 根	左右根	删除树、计算目录大小

举个例子，假设有这样一棵二叉树：

      1
     / \
    2   3
   / \
  4   5

三种遍历的结果分别是：

• 前序： 1 2 4 5 3
• 中序： 4 2 5 1 3
• 后序： 4 5 2 3 1

你仔细看看中序的结果：4 2 5 1 3。根节点 1 在中间，左边是左子树的所有节点（4 2 5），右边是右子树的节点（3）。这就是“左根右”的体现。

4.5 递归遍历的核心规律

说了这么多，其实就一句话：递归遍历的代码结构是固定的，改变 printf 的位置就能改变遍历顺序。

我建议你在学习时，不要死记硬背代码，而是理解递归的调用栈。每次递归调用，都会把当前函数的上下文压入栈中。当递归返回时，再从栈中弹出继续执行。这就是递归能“记住”走到哪里的原因。

最后，我用一张图来总结这三种遍历的流程。你可以把它当作一个“决策树”，帮助你快速判断该用哪种遍历。

嗯，递归遍历的内容就讲到这里。你只要记住：代码结构不变，printf 位置决定顺序。下次写代码的时候，先想清楚你要先处理根还是后处理根，然后直接把 printf 放在对应的位置就行。

---

公众号:蓝海资料掘金营，微信deep3321