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

Question

当我在之前从二叉搜索树中删除数字后尝试插入数字时，我收到运行时错误。我假设删除后树中的某个地方，有一个断开的路径，所以当它去插入时会发生错误。我不确定我哪里出错了。我认为它会在删除功能中。以下是插入和删除功能：

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 进行比较，最终可能会删除多个节点。