异常：删除二叉搜索树中的节点

Question

我在运行 BST 删除时出现异常。下面是我的代码片段：

Bst::node * Bst::del(node *root, int num)
    {
        if (root == NULL)
        {
            return root;
        }
        else if (num < root->data)
        {
            root->left = del(root->left, num);
        }
        else if (num > root->data)
        {
            root->right = del(root->right, num);
        }
        else
        {
            if (root->left == NULL)
            {
                node * tmp = root;
                root = root->right;
                delete tmp;
            }
            else if (root->right == NULL)
            {
                node * tmp = root;
                root = root->left;
                delete tmp;
            }
            else if (root->left == NULL && root->right == NULL)
            {
                delete root;
                root = NULL;
            }
            else
            {
                node *tmp = root;
                tmp = findMin(root->right);
                root->data = tmp->data;
                root->right = del(root->right, tmp->data);
            }
        }


        return root;
    }

void Bst::del(int num)
{
     del(root, num);
}

当我删除其他节点时一切正常，但是当我删除根节点本身时，函数 void Bst::del(int num) 从函数 Bst::node * Bst::del(node *root, int num) 获取垃圾值。当我将函数重写为

时错误得到解决

void Bst::del(int num)
        {
            root = del(root, num);
        }

问题1.为什么删除中间节点或除根节点以外的任何其他节点时有效。在调试时我发现当函数 Bst::node * Bst::del(node *root, int num) 正在执行时甚至 root 被正确删除但是当调用返回到 void Bst::del(int num) 时 root 的值没有被保留并且是垃圾。

问题2：为什么我将返回值存储在变量root中时错误得到修复？

Answer 1

在使用递归删除 BST 节点时，您必须跟踪根节点，您的做法是正确的

root->left = // ... 和 root->right = ...

然而，当展开堆栈后调用到达调用者时，根可能会被修改（当您删除根本身时）

_{这希望回答你的两个问题}

异常：删除二叉搜索树中的节点

Exception: Deletion of node in Binary Search Tree

c++

algorithm

tree

binary-search-tree