🔍 搜索算法
迷宫里找出口、地图上找路、在一堆答案里找正确的那个，都要靠「搜索」。最出名的两个办法是：一条道走到黑的 DFS，和一圈一圈往外扩的 BFS。
考纲知识点：深度优先搜索算法（DFS）
宽度优先搜索算法（也称广度优先搜索算法，BFS）
二叉树的搜索算法
宽度优先搜索算法（也称广度优先搜索算法，BFS）
二叉树的搜索算法
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 六级
- (4)掌握深度优先搜索算法（DFS）、宽度优先搜索算法（也称广度优先搜索算法，BFS）、二叉树的搜索算法的概念及应用，能够根据现实问题，选择合适的搜索算法。
📚
先学一学
花 6 分钟读完下面 5 课，再去闯关就不慌啦
1
🗺️ 搜索：在岔路口找到你要的那条路
想象你在一个巨大的游乐场里找出口：每个岔路口都是要做的选择，选了 A 路可能一路通畅，选了 B 路可能撞墙。把所有可能的选择都试一试、直到找到答案，就叫搜索。电脑解决「迷宫找路」「八皇后摆棋子」「密码猜组合」这类问题，都靠搜索。
🌲 和树的联系
从起点出发，每个选择都会分出新的岔路，画出来正好是一棵「选择树」。所以上节课学的树，就是搜索时用的地图！DFS 和 BFS 是两种逛这棵选择树的方法。
💡 口诀：搜索就是在选择树里找答案；岔路=选择，出口=答案。
2
🕳️ DFS：一条道走到黑，撞墙再回头
深度优先搜索（DFS）像勇敢的探险家：选定一条路就一直往前走，走到死路或找到出口才停下来；走不通就退回到上一个岔路口，换一条没走过的路再试。这个「往回退一步看看有没有别的路」的动作叫回溯。
🧭 走法演示：逛一棵选择树
从根 A 出发，DFS 会先钻进 A 的第一个孩子 B，B 又钻进自己的第一个孩子 D……一路扎到最深处 D，D 没路了才回头到 B，看看 B 还有没有别的孩子。简单说就是「能进就进，进不了就退」。
💡 口诀：一条道走到黑，撞了南墙就回头——这叫深度优先。
🧪 读代码：DFS 找迷宫出口（伪代码看得懂就好）
DFS 常用「自己调用自己」的写法，每到一个新格子先标记「来过」，再往上下左右试：
void dfs(int x, int y) {
if (越界 || 是墙 || 来过) return;
if (到达出口) { 找到啦; return; }
标记(x, y) 已来过;
dfs(x+1, y); // 往下走试试
dfs(x-1, y); // 往上走试试
dfs(x, y+1); // 往右走试试
dfs(x, y-1); // 往左走试试
}
if (越界 || 是墙 || 来过) return;
if (到达出口) { 找到啦; return; }
标记(x, y) 已来过;
dfs(x+1, y); // 往下走试试
dfs(x-1, y); // 往上走试试
dfs(x, y+1); // 往右走试试
dfs(x, y-1); // 往左走试试
}
💡 口诀：先检查能不能走，再标记别绕圈，然后上下左右挨个试。
3
🌊 BFS：一圈一圈往外扩，像水波
宽度优先搜索（BFS）（也叫广度优先搜索）像往平静的水面丢一颗石子：波纹一圈一圈往外扩。先看起点周围最近的一圈，再看第二圈、第三圈……谁先被波纹碰到，谁就离起点最近。
🧭 为什么 BFS 能找到「最短」路？
因为它按远近一层一层搜：第 1 圈没有出口才看第 2 圈，所以第一次碰到出口时，走的圈数一定最少。要找「最近」「最快」「最少步数」的答案，BFS 是首选。
💡 口诀：一圈一圈往外扩，谁先碰到谁最近——这叫宽度优先。
🧪 读代码：BFS 靠「排队」帮忙
BFS 用一个队列（下一页会学的先进先出结构）把「下一圈要看谁」排好队：
queue 里先放起点;
while (队列不空) {
取出队头的格子;
把它没来过的邻居都放进队尾; // 下一圈
}
while (队列不空) {
取出队头的格子;
把它没来过的邻居都放进队尾; // 下一圈
}
💡 口诀：先进先出排好队，出一个人、进一圈人，波纹就这样推出去。
4
⚖️ 易混对比：DFS vs BFS 怎么选？
📊 一张表分清两兄弟
· DFS 深度优先：一条道走到黑，撞墙回头。爱用「栈」或递归，代码好写，适合「找一条可行路、穷举所有可能」；但不保证最快找到。
· BFS 宽度优先：一圈一圈往外扩。爱用「队列」，按远近一层层来，第一次找到的一定是最短的，适合「找最近、最少步数」。
💡 口诀：要快找一条路用 DFS；要最近、最少步数用 BFS。深=往下钻，广=往外扩。
5
🌳 二叉树的搜索算法：在树上找东西怎么走
搜索不只发生在迷宫，还可能发生在「树」上。常见的两种：
🧭 第一种：把整棵树逛一遍找目标
用前面学的前序/中序/后序遍历把每个节点都看一眼，看有没有要找的数。适合普通的树，代价是把整棵树都逛完。
💡 口诀：普通树里找东西，就老老实实遍历一遍。
🧭 第二种：二叉排序树里「定向」找
如果树是上上页学的二叉排序树（左小右大），就不用傻傻逛完：从根开始，比目标大就往左走、比目标小就往右走，每一层都能丢掉一半方向。比如在根为 50 的树里找 35，35 < 50，直接去左子树。
C++ 里写出来就是递归地往左或往右钻一层，找到空还没见着就是没有。
💡 口诀：排序树里有方向，大往左、小往右，一层丢掉一半路。
🎯
闯关小锦囊 · 考点提醒
- DFS 深度优先：一条道走到黑，撞墙回溯换路，像勇敢探险家。
- BFS 宽度优先：一圈一圈往外扩，先碰到的就是最近的，适合求最短/最少步数。
- DFS 常用递归或栈；BFS 常用队列（先进先出）。
- 「找一条可行路」DFS 顺手；「找最短路径」选 BFS。
- 树的搜索：普通树靠遍历；二叉排序树靠「大往左、小往右」定向找，更快。
- 用栈写非递归前序遍历：想先访问左边，就得先压右孩子、再压左孩子（后进先出）。
🎮
学完了？来闯关！
下面 14 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。