二叉树的遍历：前序、中序、后序与层序遍历

二叉树遍历，说白了就是按照某种规则，把树里的每个节点都访问一遍。我刚开始学数据结构时，总觉得这玩意儿抽象得很，不就是走一遍吗？后来在项目中写一个表达式解析器，才发现遍历顺序选错了，整个逻辑都得重来。嗯，今天咱们就把这四种遍历方式彻底讲透。

一、递归遍历：前序、中序、后序

递归遍历的核心思想其实很简单：把一棵树拆成根、左子树、右子树三部分。访问顺序不同，就产生了三种遍历方式。我个人习惯把递归遍历想象成「打印根节点的时机」——你什么时候打印根节点，就是什么遍历。

1. 前序遍历（Preorder）

前序遍历的顺序是：先访问根节点，再遍历左子树，最后遍历右子树。我在项目中遇到过一个问题：需要把一棵二叉树序列化成字符串存到文件里，用的就是前序遍历。为什么？因为根在前，反序列化时能先重建根节点，再递归重建左右子树，逻辑最清晰。

void preorder(TreeNode* root) {
    if (root == NULL) return;  // 空树直接返回
    
    printf("%d ", root->data);  // 先访问根
    preorder(root->left);       // 再遍历左子树
    preorder(root->right);      // 最后遍历右子树
}

2. 中序遍历（Inorder）

中序遍历的顺序是：先遍历左子树，再访问根节点，最后遍历右子树。你想想看，如果这是一棵二叉搜索树（BST），中序遍历的结果是什么？没错，就是升序序列。我在做数据库索引模块时，需要把B+树叶子节点的数据按顺序输出，底层逻辑其实就是中序遍历。

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

3. 后序遍历（Postorder）

后序遍历的顺序是：先遍历左子树，再遍历右子树，最后访问根节点。说白了就是「先处理孩子，再处理父亲」。这个顺序在什么场景下特别有用？删除整棵树的时候。你得先把左右子树都删干净了，才能删根节点，否则会内存泄漏。

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

二、层序遍历：队列实现

层序遍历和前三种不一样，它不是深度优先，而是广度优先。说白了就是一层一层地往下走，先访问第一层所有节点，再访问第二层，以此类推。实现层序遍历，队列是标配。

为什么会用到队列？你想想看，访问完一个节点后，它的左右孩子需要「排队等待」被访问。这不就是先进先出（FIFO）吗？队列天然适合这个场景。

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 != NULL)
            enqueue(q, cur->left);   // 左孩子入队
        if (cur->right != NULL)
            enqueue(q, cur->right);  // 右孩子入队
    }
    
    destroyQueue(q);
}

三、四种遍历对比与知识体系

下面这张图，是我自己总结的二叉树遍历知识体系。你看一眼就能明白四种遍历之间的关系和区别。

四、实战经验总结

四种遍历方式，在实际项目中各有各的用武之地。我简单列一下，方便你以后选型时参考：

• 前序遍历：适合复制树结构、序列化/反序列化。因为根在前，重建时能先确定根。
• 中序遍历：二叉搜索树的排序输出。我在做嵌入式设备的配置参数管理时，用中序遍历把树形配置项按顺序打印出来。
• 后序遍历：释放树的内存、计算目录大小。先处理孩子再处理父亲，逻辑上最安全。
• 层序遍历：求树的宽度、按层打印、计算最短路径。我在做迷宫寻路算法时，BFS（层序思想）就是找最短路径的利器。

好了，二叉树遍历的四种方式就讲到这里。递归实现的前序、中序、后序，加上队列实现的层序，覆盖了绝大多数实际开发场景。下次你在项目中遇到树形结构，不妨想想：我到底需要哪种顺序？想清楚了再动手，代码写起来就顺了。