当前位置：首页 > news >正文

【数据结构】二叉树的遍历：层次遍历

news 2026/8/15 16:29:59

考点频率：★★★★☆（选择题常考，与三种深度优先遍历对比考查）
难度：⭐⭐
建议：重点掌握层次遍历的队列实现思路，理解其与递归遍历的区别

1️⃣ 什么是层次遍历？

层次遍历（Level Order Traversal）是按照二叉树的从上到下、从左到右的顺序，逐层访问每个节点。

打个比方：层次遍历就像按楼层检查一栋楼——先检查一楼所有房间（从左到右），再检查二楼所有房间，然后是三楼……每层都从左到右，一层一层往下走。而前序/中序/后序遍历像走迷宫——你可能先走到三楼的最深处，再回到一楼。

前面讲的前序、中序、后序遍历都属于深度优先遍历（DFS）——顺着一条路径走到头，再回溯。而层次遍历是广度优先遍历（BFS）——先访问离根近的节点，再访问离根远的节点。

2️⃣ 层次遍历的核心：队列

为什么用队列？

因为层次遍历要求“先访问的节点，先处理它的子节点”，这正好符合先进先出（FIFO）的特性——这正是队列的核心特征。

基本思路：

将根节点入队
只要队列不为空，就重复以下操作：
- 从队头取出一个节点，访问它
- 如果它有左子节点，将左子节点入队
- 如果它有右子节点，将右子节点入队

3️⃣ 层次遍历的执行过程（详细演示）

对下面这棵树进行层次遍历：

1 / \ 2 3 / \ \ 4 5 6

步骤演示：

步骤	队列（队头→队尾）	访问输出	操作
初始	`[1]`	根节点入队
第1步	`[2, 3]`	`1`	取出1，将2和3入队
第2步	`[3, 4, 5]`	`1, 2`	取出2，将4和5入队
第3步	`[4, 5, 6]`	`1, 2, 3`	取出3，将右子节点6入队（无左子节点）
第4步	`[5, 6]`	`1, 2, 3, 4`	取出4，无子节点
第5步	`[6]`	`1, 2, 3, 4, 5`	取出5，无子节点
第6步	`[]`	`1, 2, 3, 4, 5, 6`	取出6，无子节点

最终结果：1 2 3 4 5 6

4️⃣ 层次遍历的算法（伪代码）

voidLevelOrder(BiTree T){if(T==NULL)return;Queue Q;// 创建一个队列EnQueue(Q,T);// 根节点入队while(!IsEmpty(Q)){BiTNode*p=DeQueue(Q);// 取出队头Visit(p->data);// 访问该节点if(p->lchild!=NULL){EnQueue(Q,p->lchild);// 左子节点入队}if(p->rchild!=NULL){EnQueue(Q,p->rchild);// 右子节点入队}}}

时间复杂度：O(n)O(n)O(n)（每个节点入队一次、出队一次）
空间复杂度：O(n)O(n)O(n)（队列最多存储一层的节点数）

5️⃣ 层次遍历 vs 三种深度优先遍历（重要对比）

对比项	前序	中序	后序	层次遍历
遍历顺序	根→左→右	左→根→右	左→右→根	上→下，左→右
实现方式	递归（或栈）	递归（或栈）	递归（或栈）	队列
本质	深度优先（DFS）	深度优先（DFS）	深度优先（DFS）	广度优先（BFS）
根的位置	第一个	中间	最后一个	第一个
适用场景	复制树结构	二叉排序树排序	删除树	求树宽、判断完全二叉树

关键区别：深度优先遍历用栈（递归本质上就是栈），层次遍历用队列。这是两者最核心的区别。

6️⃣ 层次遍历的应用场景

应用场景	说明
求二叉树的高度	每遍历完一层，高度+1
求二叉树的宽度	统计各层节点数，取最大值
判断是否为完全二叉树	层次遍历中，如果遇到空节点后还能遇到非空节点，则不是完全二叉树
寻找二叉树中最左/最右节点	层次遍历的每一层第一个/最后一个节点
树的图形化打印	按层输出节点值