二叉树遍历：从递归到重建，一次讲透

各位同学，今天我们来啃二叉树遍历这块硬骨头。说实话，我当年学数据结构时，第一次看到前序、中序、后序的递归代码，觉得这玩意儿简直像魔法——几行代码就把整棵树摸得清清楚楚。后来在嵌入式项目中，我经常用二叉树来管理设备状态树，遍历操作几乎天天见。今天我就把压箱底的经验都抖出来。

一、递归遍历：三句话搞定

二叉树的递归遍历，说白了就是三句话的排列组合。你想想看，每个节点都做三件事：访问自己、遍历左子树、遍历右子树。这三件事的顺序一变，就变成了三种遍历方式。

代码实现更是简单到令人发指。我直接上代码，你们感受一下：

// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 前序遍历：根左右
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);   // 访问根
}

嗯，这里要注意：递归的终止条件一定是 root == NULL。我曾经见过新手写成 root->left == NULL 才返回，结果栈溢出崩了一下午。

二、层序遍历：队列才是王道

递归遍历是深度优先，层序遍历是广度优先。说白了就是一层一层往下扫，像雷达扫描一样。实现层序遍历，队列是标配。为什么？因为队列先进先出的特性，正好能保证同一层的节点按顺序被处理。

我在项目中用层序遍历做过一个设备树的可视化工具，效果拔群。代码长这样：

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

// 队列节点
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

// 队列结构
typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 入队
void enqueue(Queue* q, TreeNode* node) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = node;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

// 出队
TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    TreeNode* node = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return node;
}

// 层序遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    while (q.front != NULL) {
        TreeNode* current = dequeue(&q);
        printf("%d ", current->data);
        if (current->left) enqueue(&q, current->left);
        if (current->right) enqueue(&q, current->right);
    }
}

三、根据遍历序列重建二叉树

这个知识点很有意思。给你两个遍历序列，你能把原来的二叉树还原出来吗？我面试时经常拿这道题考人，能答对的不到一半。

核心原理：前序序列的第一个节点一定是根节点。中序序列中，根节点左边是左子树，右边是右子树。递归下去，就能重建整棵树。

看代码：

// 根据前序和中序重建二叉树
TreeNode* buildTree(int* preorder, int* inorder, int preStart, int preEnd, 
                    int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return NULL;
    
    // 前序第一个节点是根
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = preorder[preStart];
    root->left = root->right = NULL;
    
    // 在中序中找到根的位置
    int rootIndex;
    for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {
        if (inorder[rootIndex] == root->data) break;
    }
    
    int leftSize = rootIndex - inStart;  // 左子树节点数
    
    // 递归构建左右子树
    root->left = buildTree(preorder, inorder, 
                          preStart + 1, preStart + leftSize,
                          inStart, rootIndex - 1);
    root->right = buildTree(preorder, inorder,
                           preStart + leftSize + 1, preEnd,
                           rootIndex + 1, inEnd);
    
    return root;
}

四、知识体系总览

为了让大家看得更清楚，我画了一张图，把今天讲的内容串起来：

五、实战经验总结

最后，我给大家几个实战建议：

• 递归遍历：代码简洁，但深度太大时可能栈溢出。嵌入式开发中，我一般限制树深度不超过100层。
• 层序遍历：适合按层处理数据，比如打印树形结构、计算树宽。队列实现时注意内存管理。
• 重建二叉树：面试高频题，理解递归分治思想是关键。实际项目中，我常用它来做数据序列化和反序列化。