5. 二叉树的遍历（下）：层序遍历与遍历算法的应用

好，咱们接着聊二叉树的遍历。上一节我们把前序、中序、后序这三种递归遍历讲透了，今天来搞定层序遍历，以及遍历算法在实际开发中的几个经典应用。

说实话，层序遍历在我刚学数据结构那会儿，理解起来比递归遍历要费劲一些。为什么呢？因为递归遍历的思路是“一条路走到黑”，而层序遍历是“一层一层扫过去”，思维方式完全不同。但一旦你掌握了队列这个工具，层序遍历其实比递归更直观。

5.1 层序遍历的核心思想

层序遍历，说白了就是从上到下、从左到右，逐层访问每个节点。你想想看，这就像排队检票——先来的先服务，后来的排后面。这不就是典型的先进先出（FIFO）吗？

所以，层序遍历天然适合用队列来实现。我当年第一次手写层序遍历时，就在纸上画了个队列，模拟入队出队的过程，画了三遍才彻底搞明白。你也试试看，画图真的管用。

5.2 队列实现层序遍历

算法步骤其实很简单：

  1. 根节点入队
  2. 队列不为空时，循环：
    • 出队一个节点，访问它
    • 如果它有左孩子，左孩子入队
    • 如果它有右孩子，右孩子入队

嗯，就这么几行逻辑。但你别小看它，我在项目中用层序遍历做过一个“按层级打印组织架构树”的功能，效果非常好。

来看代码：

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

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

// 队列节点（用于链式队列）
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;
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// 层序遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    while (!isEmpty(&q)) {
        TreeNode* current = dequeue(&q);
        printf("%d ", current->data);
        
        if (current->left) enqueue(&q, current->left);
        if (current->right) enqueue(&q, current->right);
    }
}
我的小技巧： 如果你只是做算法题，可以用数组模拟队列，省去链式队列的指针操作。但实际项目中，链式队列更灵活，不会浪费空间。

5.3 层序遍历的流程图

下面这张图帮你理清层序遍历的完整流程。我画图时习惯把队列的变化也标出来，这样每一步都清清楚楚。

层序遍历流程图（队列实现） 二叉树： A B C D E F 队列变化过程： 步骤1：A入队 A 步骤2：A出队，B、C入队 B C 步骤3：B出队，D、E入队 C D E 步骤4：C出队，F入队 D E F 输出顺序：A → B → C → D → E → F 每层从左到右，逐层输出

5.4 遍历算法的经典应用

学遍历不能光学理论，得知道它到底能干啥。下面这两个应用，我在实际项目中都用过，一个用来算组织架构深度，一个用来统计叶子节点（也就是最底层的员工）。

5.4.1 求二叉树的深度

二叉树的深度，也叫高度，就是从根节点到最远叶子节点的路径长度。这个用递归做最简洁：

// 递归求二叉树深度
int treeDepth(TreeNode* root) {
    if (root == NULL) return 0;
    
    int leftDepth = treeDepth(root->left);
    int rightDepth = treeDepth(root->right);
    
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

这段代码的逻辑其实很巧妙——左右子树分别去算深度，取较大的那个再加1。我刚开始学的时候，总觉得递归像变魔术，后来才明白，递归就是“把问题交给更小的自己”。

核心要点： 空树深度为0，这是递归的终止条件。左右子树深度取最大值，再加根节点这一层。

当然，用层序遍历也能求深度。每遍历完一层，深度加1。这个方法在需要同时做层序遍历时很实用：

// 层序遍历求深度
int treeDepthByLevel(TreeNode* root) {
    if (root == NULL) return 0;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    int depth = 0;
    
    while (!isEmpty(&q)) {
        int levelSize = 0;
        // 统计当前层节点数
        QueueNode* temp = q.front;
        while (temp) {
            levelSize++;
            temp = temp->next;
        }
        
        // 逐一出队当前层节点，并将下一层入队
        for (int i = 0; i < levelSize; i++) {
            TreeNode* current = dequeue(&q);
            if (current->left) enqueue(&q, current->left);
            if (current->right) enqueue(&q, current->right);
        }
        depth++;
    }
    return depth;
}
我曾经踩过的坑： 用层序遍历求深度时，一定要在每层开始前记录当前队列的长度。因为队列在遍历过程中会不断变化，如果不提前记录，你根本不知道这一层有多少个节点。这个bug我调了半小时才找到。

5.4.2 求叶子节点数

叶子节点就是没有孩子的节点。统计叶子节点数，用任何一种遍历都可以，只要在访问节点时判断它是不是叶子就行。

// 递归求叶子节点数
int leafCount(TreeNode* root) {
    if (root == NULL) return 0;
    
    // 如果是叶子节点
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    // 否则递归统计左右子树的叶子节点
    return leafCount(root->left) + leafCount(root->right);
}

这个函数写起来很清爽。你想想看，叶子节点就是“左右都为空”的节点，找到它就返回1，否则继续往下找。递归的妙处就在这里——代码写出来就像在描述问题的定义本身。

用层序遍历也能统计叶子节点：

// 层序遍历求叶子节点数
int leafCountByLevel(TreeNode* root) {
    if (root == NULL) return 0;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    int count = 0;
    
    while (!isEmpty(&q)) {
        TreeNode* current = dequeue(&q);
        
        // 判断是否为叶子节点
        if (current->left == NULL && current->right == NULL) {
            count++;
        }
        
        if (current->left) enqueue(&q, current->left);
        if (current->right) enqueue(&q, current->right);
    }
    return count;
}

5.5 四种遍历方式对比

到这里，二叉树的四种遍历方式我们就全部讲完了。我整理了一张对比表，方便你复习：

遍历方式 实现工具 访问顺序 典型应用
前序遍历 递归/栈 根 → 左 → 右 复制二叉树、前缀表达式
中序遍历 递归/栈 左 → 根 → 右 二叉搜索树排序输出
后序遍历 递归/栈 左 → 右 → 根 删除二叉树、后缀表达式
层序遍历 队列 逐层从左到右 求树宽、按层打印
我的建议： 初学阶段，先把递归遍历练熟。递归是基础中的基础，面试也最爱考。层序遍历虽然思路不同，但队列实现很固定，多写两遍就能记住。

好了，这一节的内容就到这儿。层序遍历加上前面三种递归遍历，二叉树的遍历体系就完整了。下一节我们会进入更实用的部分——二叉搜索树，到时候你会发现，遍历算法在搜索树里会发挥更大的作用。

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

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