Appearance
层序遍历
层序遍历的特点
层序遍历一层一层从上往下、从左到右访问，用队列驱动：当前结点出队时，把它的左右孩子入队。这与图的 BFS 完全同构——树的层序遍历就是 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，简答题）
易错：层序遍历的结果不能单独确定一棵二叉树（需要配合中序遍历）。但层序遍历可以直接判断一棵树是否是完全二叉树：一旦遇到空结点，后续不应再出现非空结点。
相关知识
- 图的 BFS —— BFS 是层序遍历在图上的推广
- 前序遍历 / 中序遍历 / 后序遍历 —— 四种遍历方式对比（DFS vs BFS）
- 由遍历序列构造二叉树 —— 层序+中序同样可还原二叉树