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

下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void insert(TreeNode*& root, int key) {
    if (!root) {
        root = new TreeNode(key);
        return;
    }
    ________________________
}

A.

if (key < root->val)
    insert(root->left, key);
else if (key > root->val)
    insert(root->right, key);

B.

if (key < root->val)
    insert(root->right, key);
else if (key > root->val)
    insert(root->left, key);

C.

insert(root->left, key);
insert(root->right, key);

D.

insert(root->right, key);
insert(root->left, key);

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】二叉排序树｜递归

解题思维：二叉排序树的核心是左子树<根<右子树。插入时必须依据key与root->val的大小关系决定走左还是右分支，递归调用insert时参数是相应的子树指针。C/D选项无条件插入左右子树会破坏BST性质，因为它们会让同一个key出现在两个子树中；B选项左右分支判断反了，导致树序完全错误。只有A正确实现了BST的插入逻辑，通过else-if确保只走一条路径。

陷阱拆解：命题人用左右分支互换（B）、无分支判断（C/D）制造陷阱，尤其C/D看似"全面插入"实则违背BST唯一性。若只背"插入BST"结论而不理解"左小右大"的本质，就会在B和D中掉坑；else-if结构确保只走一条路径，这是BST插入的刚性约束。

反命题思维：若把插入条件改成key<=root->val，则等号会落入右子树；若改成最大堆，插入逻辑完全相反。刷到类似题时先问"这棵树靠什么规则定义结构"，答案立刻清晰。

()