C / C++ / 系统课时

用队列实现二叉树层序遍历

用队列实现二叉树层序遍历

层序遍历要按“从上到下、同层从左到右”访问二叉树。关键不是递归,而是用队列暂存已经发现、尚未访问的节点,让先进队列的节点先被处理,从而自然得到广度优先遍历顺序。

学习目标

  • 理解队列为什么能保持二叉树的层序访问顺序。
  • 用 C 语言实现节点入队、出队与层序遍历。
  • 判断层序遍历的时间复杂度与队列空间开销。

为什么层序遍历需要队列

访问根节点后,下一步应先访问它的左、右孩子;处理完左孩子后,还要继续处理此前已经发现的右孩子,再进入更深一层。这里存在“先发现、先处理”的顺序,因此 FIFO 队列正好承担待访问节点的管理工作。

层序遍历中的节点与队列变化

队列中的节点不是“当前层”的固定集合,而是所有已经发现但尚未处理的节点。每次只取队头一个节点,再把它的非空孩子放到队尾,直到队列为空。

队列怎样驱动访问顺序

层序遍历可以归纳为四个动作:

  1. 根节点非空时先入队。
  2. 取出队头节点并访问。
  3. 依次把该节点的左孩子、右孩子入队。
  4. 队列非空就继续重复出队与入队。

左孩子先于右孩子入队,才能得到常见的“同层从左到右”顺序。如果把两者次序交换,同层访问顺序也会反过来。

完整实现

下面使用固定容量的循环队列保存 TreeNode *。循环队列让已出队的位置可以再次使用,队列所需容量主要取决于遍历过程中同时等待处理的节点数。

c
#include <stdio.h>
#include <stdbool.h>

#define QUEUE_CAPACITY 64

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

typedef struct {
    TreeNode *items[QUEUE_CAPACITY];
    int front;
    int rear;
    int size;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

bool enqueue(Queue *q, TreeNode *node) {
    if (q->size == QUEUE_CAPACITY) {
        return false;
    }
    q->items[q->rear] = node;
    q->rear = (q->rear + 1) % QUEUE_CAPACITY;
    q->size++;
    return true;
}

TreeNode *dequeue(Queue *q) {
    if (q->size == 0) {
        return NULL;
    }
    TreeNode *node = q->items[q->front];
    q->front = (q->front + 1) % QUEUE_CAPACITY;
    q->size--;
    return node;
}

bool levelOrder(TreeNode *root) {
    if (root == NULL) {
        return true;
    }

    Queue q;
    initQueue(&q);
    if (!enqueue(&q, root)) {
        return false;
    }

    int first = 1;
    while (q.size > 0) {
        TreeNode *node = dequeue(&q);
        printf("%s%d", first ? "" : " ", node->value);
        first = 0;

        // 先左后右入队,保持同层从左到右的访问顺序。
        if (node->left != NULL && !enqueue(&q, node->left)) {
            return false;
        }
        if (node->right != NULL && !enqueue(&q, node->right)) {
            return false;
        }
    }

    putchar('\n');
    return true;
}

int main(void) {
    TreeNode n4 = {4, NULL, NULL};
    TreeNode n5 = {5, NULL, NULL};
    TreeNode n6 = {6, NULL, NULL};
    TreeNode n2 = {2, &n4, &n5};
    TreeNode n3 = {3, &n6, NULL};
    TreeNode n1 = {1, &n2, &n3};

    if (!levelOrder(&n1)) {
        fprintf(stderr, "queue capacity exceeded\n");
        return 1;
    }
    return 0;
}

预期输出

text
1 2 3 4 5 6

这个结果对应三层访问顺序:先根节点 1,再访问 2 3,最后访问 4 5 6。如果实际树可能很宽,应把固定容量队列改成可扩容数组或链式队列,避免容量不足。

复杂度与容易写错的地方

每个节点只会入队一次、出队一次,因此包含 nn 个节点的二叉树,层序遍历时间复杂度是 O(n)O(n)。队列的峰值大小取决于某一时刻等待处理的节点数,通常可用树的最大宽度 ww 表示为空间复杂度 O(w)O(w)。

实现时最常见的错误是出队后忘记把孩子入队、左右孩子入队顺序写反,或在空树时直接访问根节点。只要始终维持“出队一个、访问一个、孩子入队”的循环,队列就会把树的层级关系转换成稳定的访问顺序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用队列实现二叉树层序遍历

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通