考点频率★★★★☆选择题常考与三种深度优先遍历对比考查难度⭐⭐建议重点掌握层次遍历的队列实现思路理解其与递归遍历的区别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 64️⃣ 层次遍历的算法伪代码voidLevelOrder(BiTree T){if(TNULL)return;Queue Q;// 创建一个队列EnQueue(Q,T);// 根节点入队while(!IsEmpty(Q)){BiTNode*pDeQueue(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求二叉树的宽度统计各层节点数取最大值判断是否为完全二叉树层次遍历中如果遇到空节点后还能遇到非空节点则不是完全二叉树寻找二叉树中最左/最右节点层次遍历的每一层第一个/最后一个节点树的图形化打印按层输出节点值例题利用层次遍历判断完全二叉树完全二叉树的特点在层次遍历中一旦遇到NULL空位后面不应该再出现非空节点按层遍历时如果遇到空节点则记录一个标志位若之后又遇到非空节点说明不是完全二叉树7️⃣ 经典例题例题1对下面这棵二叉树进行层次遍历结果是什么A / \ B C / \ \ D E F解析第1层A第2层B, C第3层D, E, F层次遍历结果A B C D E F答案A B C D E F例题2某二叉树的层次遍历序列为1 2 3 4 5 6这棵二叉树不可能是 。A. 满二叉树B. 完全二叉树C. 只有右子树的树D. 以上都有可能解析1 2 3 4 5 6是层次遍历序列它描述了各层从左到右的访问顺序。层次遍历序列不能唯一确定一棵二叉树但它必须符合“上层先于下层、左兄弟先于右兄弟”的约束。只有右子树的树每个节点只有右子节点的层次遍历为1 2 3 4 5 6完全可能。选D。例题3判断层次遍历可以使用栈来实现。 解析错误。层次遍历使用队列FIFO来实现广度优先搜索。如果使用栈会变成深度优先遍历。8️⃣ 记忆口诀层次遍历用队列根节点先入队。出队访问后入子左先右后别弄反。深度优先用递归广度优先用队列。9️⃣ 小测验评论区对答案用层次遍历求一棵二叉树的高度时每遍历完一层需要 。A. 将队列清空B. 在队列末尾插入一个特殊标记如NULLC. 重新从根节点开始D. 将当前层的所有节点出队后再统计答案下期公布。本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #层次遍历 #二叉树 #数据结构 #软考备考