GESP 六级 · GESP 202406 C++ 六级 第 15 题

在上题的树中搜索数值 $3$ 时，采用深度优先搜索一共比较的节点数为（ ）。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】二叉搜索树遍历｜深度优先搜索｜节点比较次数

1. 🎯 考纲定位：GESP 六级 C++ 模块的"二叉树遍历与搜索"考点。命题人卡住的是学生只背"叶子节点即终止"的结论，却忽略 BST 搜索中每一步都要比较的值，以及非叶子节点也可能成为比较终点。

2. 🧠 解题思维：在 BST 中搜索 3 时，从根 12 开始，12>3 转向左子树 6，6>3 继续左子树 4，4>3 再左子树为空，比较节点数为 4。关键观察是：每次比较都决定下一步方向，而非只看是否找到目标。这一类题的通法是记录从根到目标（或空）的路径长度，BST 搜索的比较次数等于路径长度 +1。

3. 🪤 陷阱拆解：A 项 2 是只比较了 12 和 6；B 项 3 误以为 4 是叶子节点；D 项 5 多算了某个子节点。最阴险的细节：搜索 3 时，4 不是叶子节点，但它的左子树为空，因此比较节点数为 4。如果你只背结论，就会掉进"叶子节点即终止"的陷阱。

4. 🔄 反命题思维：若将搜索值改为 7，路径变为 12-6-10-7，比较节点数仍为 4，说明命题人通过改变目标值来检验对 BST 结构的理解。刷到类似题时，先问自己"命题人想考我什么"。