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

二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组（假设数组中没有数值相等的元素），构造一个对应的二叉搜索树，横线上应填写（ ）：

// 定义二叉树的结点结构
struct tree_node {
    int val;
    tree_node* left;
    tree_node* right;

    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {
    if (root == nullptr) {
        return new tree_node(val);
    }

    ________________________ // 在此处填入代码

    return root;
}

// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {
    tree_node* root = nullptr;

    for (int i = 0; i < size; ++i) {
        root = insert(root, arr[i]);
    }

    return root;
}


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

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

【考点】二叉搜索树构造｜递归插入逻辑｜指针操作

🎯 考纲定位：GESP 六级《算法与数据结构》模块，属于指针操作进阶题。命题人专门卡住考生对"递归返回值必须赋值"这一细节的掌握程度，这是区分六级与五级的关键分水岭。

🧠 解题思维：insert 函数本质是递归插入。先判断根是否为空（直接返回新节点），若不为空则比较 val 与 root->val 大小：小于则递归插入左子树，大于则递归插入右子树。最关键的一步——递归调用 insert(root->left, val) 或 insert(root->right, val) 后，必须把返回值赋给对应指针（root->left = ... 或 root->right = ...），否则新节点永远悬空，树结构断裂。

🪤 陷阱拆解：选项 A 正确写法是同时处理左右递归并赋值。若只写 left 或 right 递归不赋值，新节点丢失；若用循环代替递归，会陷入死循环；若漏掉比较条件直接递归，会重复插入。命题人专挖"递归返回值不用"的坑——考生容易只调用 insert 却忽略返回值，导致构造出的树不完整。

🔄 反命题思维：若把 insert 改成循环实现，需手动控制 while 遍历直到找到空位再插入；若数组含重复值，题目会明确说明如何处理（BST 通常含重复则右子树可存相等值）。刷到二叉搜索树题，先想清楚递归返回值代表什么。