GESP 六级 · GESP 202409 C++ 六级 第 23 题

在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。

BFS 使用队列，按层次逐层遍历，适合求最短路径（边权为1时）。核心：标记已访问，避免重复入队。

BFS 入队后立即标记已访问，防止重复入队。队列为空时搜索结束。注意区分树的BFS（无需visited标记）和图的BFS。

【考点】树的遍历｜队列｜栈

🎯 考纲定位 GESP 六级《数据结构》模块。命题人卡住的是"遍历方法"与"辅助结构"的对应关系——90%考生能背出"DFS用栈，BFS用队列"，但遇到非递归实现时容易混淆，这里直接考栈的用途，就是筛掉死记硬背的人。

🧠 解题思维 BFS是层次遍历，必须按"先入先出"顺序处理节点，否则先访问的节点后访问的子孙会先被处理，破坏层次性。非递归实现时，队列天然支持FIFO，每次弹出当前层节点，再把其子节点入队，下一轮再弹出下一层，完美匹配。栈是LIFO，若用它实现BFS，先入的节点后出，导致深度优先的访问顺序，完全违背BFS定义。

🪤 陷阱拆解 陷阱在于"非递归"三个字。递归BFS看似需要栈（系统调用栈），但非递归版本必须显式使用队列。命题人故意用"通常使用栈"来制造混淆，利用考生对"栈"与"递归"的刻板关联，诱导选了A。

🔄 反命题思维 如果把题目改成"深度优先搜索的非递归实现通常使用什么辅助结构？"答案就是A（栈）。刷到这类题时，先问自己"考的是遍历顺序还是辅助结构"，别被"非递归"带偏。