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

对上题中的二叉搜索树，当输入数组为 $[5,3,7,2,4,6,8]$ 时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到的输出是（ ）。

#include <iostream>
using namespace std;

// 遍历二叉搜索树，输出结点值
void traversal(tree_node* root) {
    if (root == nullptr) {
        return;
    }

    traversal(root->left);
    cout << root->val << " ";
    traversal(root->right);
}

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

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

【考点】二叉搜索树构建｜中序遍历

1. 考纲定位：六级《数据结构》模块第2章核心考点。命题人卡住的是"BST插入顺序≠输出顺序"这一认知断层，学生常把构建过程误认为遍历结果，混淆"怎么建"与"怎么读"。

2. 解题思维：先识别递归函数为"左-根-右"的经典中序遍历模板。按数组顺序插入构建BST：5为根，3<5左插，7>5右插，2<5且<3左插，4>5且<7右插，6<7且>4左插，8>7右插，形成完整结构。中序遍历必然输出有序序列，故选B。

3. 陷阱拆解：A项是数组原序，命题人利用"代码先出现即先输出"的直觉误导。C、D项是前序遍历结果，偷换"左-根-右"为"根-左-右"。若只看根节点5，会误选A，却忽略递归调用顺序。

4. 反命题思维：若把代码改成先中序再根再右，输出仍为B；若改成后序，输出会完全不同。刷到类似题，先问"遍历顺序是否匹配代码"，避免默认认为输出顺序等于输入顺序。