GESP 六级 · GESP 202412 C++ 六级 第 12 题

阅读以下二叉树的广度优先搜索的代码，横线上应填写（ ）。

#include <queue>
void bfs(TreeNode* root) {
    if (root == NULL) return;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        ________________________ // 在此处填入代码
        cout << node->val << " ";
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。

区分排列（考虑顺序，$P(n,m)$）和组合（不考虑顺序，$C(n,m)$）。注意特殊元素优先处理、正难则反等计数技巧。

【考点】BFS 遍历｜队列操作（front/pop）｜栈队列混淆

🎯 考纲定位 本题考查《GESP 六级大纲》图论/树算法模块中的二叉树遍历与 STL 容器操作。命题人卡住的是学生"看到队列就条件反射用 top()"——这是 stack 的专属 API，queue 根本没有 top() 方法，属于容器语义混淆陷阱。

🧠 解题思维 BFS 的核心是"先进先出"：队列里存的是待访问节点，每轮必须取出队首节点处理，再把它两个子节点推回去。循环体里要干三件事：取队首元素、打印值、推子节点。C++ 里 queue 只有 front() 读队首 + pop() 删队首，因此横线处必须同时写这两行。

🪤 陷阱拆解 A/B 错在哪？q.top() 在 queue 里根本不存在，这是 stack 的 API，编译器直接报错或静默错误（若混用头文件）。C 错在哪？只 front 不 pop，队列永远取不到新元素，while(!q.empty()) 变成死循环。命题人用前两个选项考容器语义，用 C 选项考逻辑闭环——只读不删，队列遍历必挂。

🔄 反命题思维 若把 queue 换成 stack，横线应填 q.top(); q.pop();，遍历顺序变 DFS 后序。刷到类似题先问自己：这题考的是容器 API 的边界（front/top/pop）还是算法语义（BFS/DFS）？