14、二叉树与递归：二叉树的创建、前中后序遍历、层序遍历、递归思想

二叉树，说白了就是每个节点最多有两个孩子。左孩子、右孩子，就这么简单。但你别小看这个结构，我做了十几年嵌入式开发，从文件系统到表达式解析，从哈夫曼编码到路由查找，到处都有它的影子。

递归呢？它是解决二叉树问题的灵魂。你想想看，一棵树拆成根节点加左右子树，左右子树又各自是更小的树——这不就是递归的天然舞台吗？

14.1 二叉树的定义与节点结构

先看节点长什么样。每个节点存一份数据，再加两个指针，分别指向左孩子和右孩子。

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

嗯，这里要注意：left 和 right 都是指针。如果某个孩子不存在，就指向 NULL。这是递归终止的关键条件。

14.2 二叉树的创建

创建二叉树，最直观的方式就是递归创建。我给你一个前序序列，比如 1 2 4 -1 -1 5 -1 -1 3 -1 -1，其中 -1 表示空节点。递归函数读到 -1 就返回 NULL，否则创建节点，再递归创建左右子树。

TreeNode* createTree(int arr[], int *idx) {
    if (arr[*idx] == -1) {
        (*idx)++;
        return NULL;
    }
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = arr[*idx];
    (*idx)++;
    node->left = createTree(arr, idx);
    node->right = createTree(arr, idx);
    return node;
}

我个人习惯用 -1 做哨兵。你在实际项目中也可以用 0 或 INT_MIN，只要保证数据域里不会出现这个值就行。

小技巧： 创建时用二级指针或指针的引用传递索引，这样递归过程中索引能持续递增。我见过不少新手用全局变量，多线程环境下容易出问题。

14.3 前中后序遍历

三种遍历方式，区别就在于访问根节点的时机。

  • 前序遍历： 根 → 左 → 右
  • 中序遍历： 左 → 根 → 右
  • 后序遍历： 左 → 右 → 根

代码写起来非常对称，你感受一下：

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);   // 后：最后访问根
}

我曾经在调试一个表达式求值器时，用后序遍历构建语法树，再用中序遍历输出中缀表达式。那次排查一个括号匹配的 bug，硬是画了半天的树形图。后来发现是递归返回时少处理了一层运算符优先级——嗯，从那以后我对递归的「归」阶段格外敏感。

核心理解： 递归遍历的本质是「调用栈的压入与弹出」。前中后序只是改变了 printf 在递归调用中的位置，其他逻辑完全一样。

14.4 层序遍历

层序遍历就不一样了。它不依赖递归，而是用队列。一层一层从上往下、从左往右扫过去。

void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    Queue *q = createQueue();
    enqueue(q, root);
    while (!isEmpty(q)) {
        TreeNode *cur = dequeue(q);
        printf("%d ", cur->data);
        if (cur->left)  enqueue(q, cur->left);
        if (cur->right) enqueue(q, cur->right);
    }
    destroyQueue(q);
}

为什么层序要用队列？因为它是广度优先搜索（BFS）的思想。递归是深度优先（DFS），天然适合用栈（系统调用栈）。你想想看，层序要求「先看到的先处理」，这不就是先进先出吗？队列正好。

注意： 层序遍历的队列实现要小心内存泄漏。我在一个嵌入式项目里用过静态数组模拟环形队列，省去了动态分配的开销，但要注意队列大小要提前算好——最坏情况下一层可能有 n/2 个节点。

14.5 递归思想：从二叉树看递归的本质

递归，说白了就是「自己调用自己，但规模越来越小」。二叉树是理解递归最好的教材，因为它的定义本身就是递归的：

  • 空树是二叉树
  • 一个根节点加上左右两棵二叉树，还是二叉树

你看，定义里就出现了「二叉树」自己。这就是递归的数学基础——归纳定义。

写递归函数，记住三个要素：

  1. 终止条件： 什么时候停下来？一般是节点为 NULL。
  2. 递推关系： 当前节点和子节点之间的关系是什么？比如求树的高度：height = 1 + max(leftHeight, rightHeight)。
  3. 返回值与副作用： 递归返回什么？是值（如高度），还是操作（如打印）？

举个例子，求二叉树的高度：

int treeHeight(TreeNode *root) {
    if (root == NULL) return 0;                     // 终止条件
    int leftH = treeHeight(root->left);             // 递：左子树高度
    int rightH = treeHeight(root->right);           // 递：右子树高度
    return (leftH > rightH ? leftH : rightH) + 1;   // 归：合并结果
}

我曾经在面试一个候选人时，让他手写这个函数。他写对了，但问他「为什么递归能正确返回？」他答不上来。其实关键就在于：每一层递归都假设子问题已经解决，然后只处理当前层。这就是递归的「信任跳跃」——你相信递归函数在子问题上能正确工作。

避坑指南： 我曾经在深度很大的树上递归，导致栈溢出。嵌入式环境栈空间通常只有几 KB，递归深度超过几百层就可能崩。解决方案有两个：一是改用迭代（显式栈），二是增大栈空间（但治标不治本）。对于平衡二叉树，深度是 log n，基本安全；对于退化成链表的树，深度是 n，递归就危险了。

14.6 知识体系总览

下面这张图把二叉树与递归的核心知识点串了起来。你一看就明白：创建、遍历、递归思想，这三者如何相互支撑。

二叉树与递归 二叉树的创建 递归创建 哨兵标记空节点 二叉树的遍历 前序：根左右 中序：左根右 后序：左右根 层序：队列实现BFS 递归思想 终止条件 递推关系 信任跳跃 递归是二叉树的天然表达方式

14.7 总结

二叉树和递归，就像鱼和水。你理解了递归，二叉树就只剩下一层窗户纸；你掌握了二叉树，递归的「分而治之」思想也就刻在骨子里了。

我个人建议你多画图。每次递归调用，在纸上画一个节点，标出当前栈帧。画上十棵树，递归就不再神秘。我在带新人时，发现他们最大的障碍不是语法，而是「不敢信任递归」。其实你只要把终止条件写对，把递推关系写对，剩下的交给计算机就好。

练习建议： 自己实现一个二叉搜索树（BST），然后分别用递归和迭代完成插入、查找、删除。删除操作是递归的经典应用——你会深刻体会到「归」阶段的精妙。

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

← 上一章 📖 返回目录 下一章 →