C / C++ / 系统课时
用队列实现二叉树层序遍历
用队列实现二叉树层序遍历
层序遍历要按“从上到下、同层从左到右”访问二叉树。关键不是递归,而是用队列暂存已经发现、尚未访问的节点,让先进队列的节点先被处理,从而自然得到广度优先遍历顺序。
学习目标
- 理解队列为什么能保持二叉树的层序访问顺序。
- 用 C 语言实现节点入队、出队与层序遍历。
- 判断层序遍历的时间复杂度与队列空间开销。
为什么层序遍历需要队列
访问根节点后,下一步应先访问它的左、右孩子;处理完左孩子后,还要继续处理此前已经发现的右孩子,再进入更深一层。这里存在“先发现、先处理”的顺序,因此 FIFO 队列正好承担待访问节点的管理工作。

队列中的节点不是“当前层”的固定集合,而是所有已经发现但尚未处理的节点。每次只取队头一个节点,再把它的非空孩子放到队尾,直到队列为空。
队列怎样驱动访问顺序
层序遍历可以归纳为四个动作:
- 根节点非空时先入队。
- 取出队头节点并访问。
- 依次把该节点的左孩子、右孩子入队。
- 队列非空就继续重复出队与入队。
左孩子先于右孩子入队,才能得到常见的“同层从左到右”顺序。如果把两者次序交换,同层访问顺序也会反过来。
完整实现
下面使用固定容量的循环队列保存 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。如果实际树可能很宽,应把固定容量队列改成可扩容数组或链式队列,避免容量不足。
复杂度与容易写错的地方
每个节点只会入队一次、出队一次,因此包含 个节点的二叉树,层序遍历时间复杂度是 。队列的峰值大小取决于某一时刻等待处理的节点数,通常可用树的最大宽度 表示为空间复杂度 。
实现时最常见的错误是出队后忘记把孩子入队、左右孩子入队顺序写反,或在空树时直接访问根节点。只要始终维持“出队一个、访问一个、孩子入队”的循环,队列就会把树的层级关系转换成稳定的访问顺序。
按自己的节奏,确认真正理解。