BST插入删除操作后节点位置异常问题求助

你的问题核心是删除节点后BST结构被错误修改，导致后续插入的节点位置计算错误，根源在于代码中存在多个逻辑错误，我们逐一拆解修复：

1. findMin函数缺少返回值 #

你的findMin在递归时没有返回结果，导致函数返回野指针，直接破坏了删除操作的核心逻辑：

// 错误版本
BSTNode *findMin(BSTNode *root) {
    if(root->left ==NULL) {
        return root;
    }
    else findMin(root->left); // 没有返回递归结果，返回值未定义
}

修复后：

// 正确版本
BSTNode *findMin(BSTNode *root) {
    if(root->left == NULL) {
        return root;
    }
    return findMin(root->left); // 递归返回最小值节点
}

2. 删除函数的叶子节点判断错误 #

你用root->left == root->right ==NULL判断叶子节点，这不符合C++逻辑（先判断root->left == root->right得到bool值，再和NULL比较，永远为false），导致叶子节点无法正确删除：

// 错误版本
if(root->left == root->right ==NULL) {

修复后：

// 正确版本
if(root->left == NULL && root->right == NULL) {

3. search函数的递归逻辑错误 #

原search函数依赖全局变量position，递归时没有回溯位置，且未正确返回递归结果，导致位置计算混乱。我们改用参数传递当前位置（避免全局变量副作用）：

// 正确版本：用引用传递当前位置
bool search(BSTNode *root, int data, ll &pos) {
    if(root == NULL) {
        return false;
    }
    if(data == root->data) {
        return true;
    } else if(data < root->data) {
        pos = 2 * pos;
        return search(root->left, data, pos);
    } else {
        pos = 2 * pos + 1;
        return search(root->right, data, pos);
    }
}

同时在main函数中调用时，要初始化位置并传递引用：

if(c=='i') {
    root = insert(root,input);
    ll pos = 1;
    search(root, input, pos);
    cout << pos << endl;
}
if(c=='d') {
    ll pos = 1;
    search(root, input, pos);
    root = delet(root,input); // 必须接收删除函数的返回值，避免根节点丢失
    cout << pos << endl;
}

4. 删除函数的返回值处理错误 #

原delet函数部分分支没有返回值，导致未定义行为，且删除根节点时无法更新root指针：

// 正确版本
BSTNode* delet(BSTNode* root,int data) {
    if(root == NULL) {
        return NULL;
    }
    else if(data<root->data) {
        root->left = delet(root->left,data);
    }
    else if(data>root->data) {
        root->right = delet(root->right,data);
    }
    else // 找到要删除的节点
    {
        // CASE 1: 叶子节点
        if(root->left == NULL && root->right == NULL) {
            delete root;
            root = NULL;
        }
        // CASE 2: 只有右孩子
        else if(root->left == NULL) {
            BSTNode *temp= root;
            root = root->right;
            delete temp;
        }
        // CASE 3: 只有左孩子
        else if(root->right == NULL) {
            BSTNode *temp=root;
            root= root->left;
            delete temp;
        }
        // CASE 4: 有两个孩子
        else {
            BSTNode *temp = findMin(root->right);
            root->data = temp->data;
            root->right = delet(root->right, temp->data);
        }
        return root;
    }
    return root;
}

为什么会出现位置计算错误？ #

根本原因是findMin函数的错误导致删除9时，程序用野指针修改了节点值，完全破坏了BST结构。后续插入14时，错误的树结构让search函数计算出错误位置。

修复所有错误后，删除9的操作会正确执行：将9替换为其右子树的最小值11，删除原11节点，此时树结构符合预期。插入14时会被正确放到19的右子树，位置为2*(2*(2*2+1)+1)+1 = 23（如果期望用左子树最大值替换9，可将删除逻辑改为调用findMax(root->left)，树结构会对应调整）。

内容的提问来源于stack exchange，提问作者Harshal Sharma