在先前已在 BST 中删除节点后尝试插入时出现运行时错误

Question

当我尝试在之前从二叉搜索树中删除一个数字后插入一个数字时出现运行时错误。我假设在删除后树中的某处存在一条断开的路径，因此当它插入时会发生错误。我不确定我哪里出错了。我假设它会在 remove 函数中。下面是插入和删除函数：

void BST::insert(int x)
{
    TreeNode * v = root;
    if (root == NULL)
    {
        root = new TreeNode(x);
        return;
    }
    if (x == v->key)
    {
        return;
    }
    while (x != v->key)
    {

        if (x < v->key)
        {
            if (v->left != NULL)
            {
                v = v->left;

            }
            else
            {
                v->left = new TreeNode(x);
                return;
            }
        }
        if (x > v->key)
        {
            if (v->right != NULL)
            {
                v = v->right;
            }
            else
            {
                v->right = new TreeNode(x);
                return;
            }
        }
    }
}

void BST::remove(TreeNode * & v, int x)
{
    if (v == NULL)
        return;
    if (x < v->key)
    {
        remove(v->left, x);
    }
    if (x > v->key)
    {
        remove(v->right, x);
    }
    if (x == v->key)
    {
        if (v->left == NULL && v->right == NULL)
        {
            delete v;
            return;
        }
        if (v->left == NULL)
        {
            TreeNode *temp = v;
            v = v->right;
            delete temp;
        }
        if (v->right == NULL)
        {
            TreeNode * temp = v;
            v = v->left;
            delete temp;
        }
        if (v->left != NULL && v->right != NULL)
        {
            TreeNode * u = v->right;
            while (u->left != NULL)
            {
                u = u->left;
            }
            v->key = u->key;
            remove(u, u->key);          
        }
    }
}

Answer 1

此代码存在多个问题，并且有多种方法可以解除对无效指针的引用。

在 remove 中，找到匹配键后，如果节点没有子节点，则将其删除，但不要清空指向已删除节点的指针，留下悬空引用。

您有几个系列的 if 语句，应该是 else if。如果 v->left == NULL，您将 v 更改为指向 right 节点，然后将此新值的 right 与 NULL 进行比较，最终可能会删除多个节点。

在先前已在 BST 中删除节点后尝试插入时出现运行时错误

runtime error when trying to insert after a node has previously been removed in a BST

c++

insert

binary-search-tree