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

阅读以下二叉树的广度优先搜索代码:

#include <iostream>
#include <queue>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 宽度优先搜索（BFS）迭代实现
TreeNode* bfs(TreeNode* root, int a) {
    if (root == nullptr) return nullptr;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if (node->val == a)
            return node;

        cout << node->val << " "; // 先访问当前节点

        if (node->left) q.push(node->left); // 将左子节点入队
        if (node->right) q.push(node->right); // 将右子节点入队
    }
    return nullptr;
}

使用以上算法，在以下这棵树搜索数值 $20$ 时，可能的输出是（ ）。


仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】队列｜树形结构遍历｜二叉树

考纲定位：GESP 六级「树形结构遍历」模块，专测 BFS 执行流程。命题人卡住的是学生常把队列内容误当成已打印序列，忽视「先入队后打印」的 FIFO 本质，导致层序与打印顺序混淆，且容易把左右子节点顺序搞反。（ 命题）

解题思维：队列里存的是待访问节点，打印顺序等于出队顺序。根 5 先入队，出队打印 5，再进 2、-4；接着出队 2 打印，进 17、3；再出队 -4 打印，进 9、17；出队 17 打印，进 9、17……直到遇到值 20 才返回。因此输出是 BFS 层序打印序列（GESP 六级）。

陷阱拆解：A 把第二层孩子错排成 2‑4‑3 而非 2‑17‑3；B 是深度优先或完全逆序；C 看似把 2 的子节点提前，实则正确对应队列出队顺序。只背结论不模拟队列，必选错。

反命题思维：若改为先打印再入队，或左右子节点交换入队顺序，输出会完全不同。刷到 BFS 题先想「队列里到底有哪些节点」，再模拟出队顺序。