Appearance
层序遍历
为什么需要层序遍历
前序、中序、后序遍历本质上都是深度优先搜索（DFS），它们沿着某条路径一直深入到叶子节点后才回溯。然而很多场景需要逐层处理节点，例如：按层打印二叉树、求树的最大宽度、判断是否为完全二叉树等。
层序遍历采用**广度优先搜索（BFS）**策略，借助队列实现"先访问离根最近的节点"，是 408 考研中二叉树遍历的重要组成部分。
核心思想
层序遍历的核心特点：
- 逐层访问：从根节点所在的第 1 层开始，自上而下、自左而右依次访问每个节点
- 借助队列：利用队列的 FIFO 特性，保证同一层节点按从左到右的顺序被处理
- BFS 思想：每次从队列取出一个节点后，将其左、右孩子依次入队，自然实现"由近及远"的访问顺序
遍历过程示意：
A 第 1 层: A
/ \
B C 第 2 层: B C
/ \ \
D E F 第 3 层: D E F
层序遍历结果: A → B → C → D → E → F层序遍历流程图
层序遍历借助队列的 FIFO 特性，保证同层节点从左到右依次被访问，实现逐层遍历。
交互可视化
通过下方的交互动画，你可以逐步观察层序遍历的执行过程：
操作详解
算法思路
关键步骤：
- 若树为空，直接返回
- 将根节点入队
- 当队列不为空时，循环执行：
- 队头节点出队，访问该节点
- 若该节点有左孩子，左孩子入队
- 若该节点有右孩子，右孩子入队
- 队列为空时，遍历结束
队列辅助实现
使用顺序队列（循环队列）辅助实现层序遍历：
c
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void LevelOrder(BiTree T) {
if (T == NULL) return;
BiTree queue[MAXSIZE]; // 辅助队列
int front = 0, rear = 0;
queue[rear++] = T; // 根节点入队
while (front != rear) {
BiTree p = queue[front++]; // 队头出队
visit(p); // 访问当前节点
if (p->lchild != NULL)
queue[rear++] = p->lchild; // 左孩子入队
if (p->rchild != NULL)
queue[rear++] = p->rchild; // 右孩子入队
}
}注意：上述代码为简化写法，实际考试中队列可能需要用循环队列或手写队列结构来避免假溢出。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个节点恰好入队、出队各一次 |
| 空间复杂度 | O(n) | 最坏情况队列中最多存放 ⌈n/2⌉ 个节点（最后一层） |
空间复杂度：辅助队列的最大长度取决于树的最大宽度。对于完全二叉树，最后一层节点数约为 n/2，因此空间复杂度为 O(n)。
考研高频考点
- ⭐ 给定二叉树写出层序遍历序列（选择题/填空题高频）
- ⭐ 层序遍历的队列变化过程（手动模拟入队出队，选择题常考）
- ⭐ 利用层序遍历判断完全二叉树（算法设计题：遇到空节点后不应再出现非空节点）
- ⭐ 求二叉树的最大宽度（记录每层节点数，取最大值）
- 层序遍历与 BFS 的关系（概念题）
- 层序遍历与前序/中序/后序遍历的对比（DFS vs BFS，简答题）