13、递归与树：二叉树的前序、中序、后序遍历的递归实现

树结构，尤其是二叉树，是递归思想最天然的舞台。你想想看，一棵树的每个节点，往下看又是一棵子树——这不就是递归的「自己调用自己」吗？

我个人习惯把二叉树遍历比作「拜访一座家族庄园」。前序、中序、后序，说白了就是三种不同的拜访顺序。今天我们就用递归这把钥匙，把这三扇门一一打开。

13.1 二叉树的结构定义

先搭个架子。在C语言里，二叉树节点通常这样定义：

typedef struct TreeNode {
    int data;                   // 数据域
    struct TreeNode *left;      // 左孩子指针
    struct TreeNode *right;     // 右孩子指针
} TreeNode;

嗯，这里要注意：left 和 right 都是指向同类型节点的指针。这就是递归定义——节点里藏着节点，无穷嵌套。

13.2 前序遍历（Preorder）

前序的规则很简单：先访问根节点，再遍历左子树，最后遍历右子树。

用递归写出来，几乎就是翻译这句话：

void preorder(TreeNode *root) {
    if (root == NULL) {
        return;                 // 空树，啥也不干
    }
    printf("%d ", root->data); // 访问根
    preorder(root->left);       // 遍历左子树
    preorder(root->right);      // 遍历右子树
}

你看，代码只有几行。但它的执行过程，其实是一层一层往下钻，再一层一层往回返。我曾经调试一个前序遍历的bug，发现打印结果少了一个节点——最后发现是左子树指针被意外改成了NULL。嗯，指针操作一定要小心。

13.3 中序遍历（Inorder）

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

代码几乎就是前序的微调：

void inorder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);        // 先走左边
    printf("%d ", root->data); // 再访问根
    inorder(root->right);       // 最后走右边
}

中序有一个重要特性：对于二叉搜索树（BST），中序遍历的结果是升序的。这个特性我在做数据库索引模块时用过——直接把树的中序结果输出，就是排好序的数据。

13.4 后序遍历（Postorder）

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

void postorder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);      // 左
    postorder(root->right);     // 右
    printf("%d ", root->data); // 根
}

后序在什么场景下用？删除整棵树的时候。你得先把孩子删掉，才能删父亲。否则先删了父亲，孩子就找不到了——内存泄漏就是这么来的。

13.5 三种遍历的对比

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

13.6 递归过程可视化

光看代码可能还不够直观。我画了一张图，展示一棵小树的前序遍历过程：

从图中可以清楚看到：前序先访问根A，然后一头扎进左子树B，再扎进D……直到左边走完，才回头走右边。这就是递归的「深度优先」本质。

13.7 递归的底层：函数调用栈

你可能会问：递归到底是怎么记住「回头路」的？

答案是函数调用栈。每次递归调用，系统会把当前函数的局部变量和返回地址压入栈中。等子调用返回后，再从栈里弹出，继续执行。

举个例子，前序遍历 A(B(D,E),C(,F)) 的栈变化：

1. 调用 preorder(A)，打印A，压栈A，调用 preorder(B)
2. 打印B，压栈B，调用 preorder(D)
3. 打印D，压栈D，调用 preorder(NULL)，返回
4. 弹出D，调用 preorder(NULL)，返回
5. 弹出B，调用 preorder(E)，打印E……

栈深度就是树的深度。如果树有1000层，递归就会压1000层栈——小心栈溢出。我在嵌入式项目里就遇到过，树深度只有200层，但系统栈太小，直接崩了。后来改成了非递归（迭代）实现才解决。

13.8 完整示例代码

最后，给一个完整的可运行示例。你可以在自己的机器上跑跑看：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建节点
TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 前序
void preorder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// 中序
void inorder(TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 后序
void postorder(TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

int main() {
    // 构建一棵树
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);

    printf("前序: ");
    preorder(root);
    printf("\n");

    printf("中序: ");
    inorder(root);
    printf("\n");

    printf("后序: ");
    postorder(root);
    printf("\n");

    // 释放内存（后序释放）
    // 实际项目中需要写一个 destroyTree 函数
    return 0;
}

输出结果：

前序: 1 2 4 5 3 6
中序: 4 2 5 1 3 6
后序: 4 5 2 6 3 1

你可以对照前面的图，看看顺序是不是一致。

13.9 小结

递归遍历二叉树，说白了就是三句话：

• 前序：先干活（访问根），再往左，再往右
• 中序：先往左，再干活，再往右
• 后序：先往左，再往右，最后干活

代码几乎一模一样，只是 printf 的位置不同。但背后的执行流程、栈的变化、适用的场景，却各有讲究。

我个人觉得，理解这三种遍历，是掌握递归思想的一道分水岭。跨过去，后面再看树的更多操作（比如求深度、判断平衡、构建表达式树），就会觉得顺理成章。

---

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