c++ - 试图从二叉搜索树中删除一个节点

Question

当我尝试在删除节点后显示我的树时出现内存错误。
这是我的移除(删除)方法:

void binarySearchTree::remove(int x, node * r)
{
    bool found = false;
    node * previous = NULL;

    if (root == NULL)
    {cout << "Tree is empty. Nothing to remove." << endl; return;}

    while (!found)
    {
        if (x < r->data)
        {
            previous = r;
            r = r->left;
        }
        else if (x > r->data)
        {
            previous = r;
            r = r->right;
        }
        else
            found = true;
    }


    if (r->left == NULL && r->right == NULL)        //case 1: node to be deleted is a leaf (no children)
    {
        delete r;
        return;
    }
    else if(r->left == NULL && r->right != NULL)    //case 2: node only has a right child
        previous->right = r->right;
    else if (r->left != NULL && r->right == NULL)   //case 2: node only has a left child
        previous->left = r->left;
    else
    {                                               //case 3: node has two children
        node * minNode = findMinNode(r->right);     //finds min node in the right sub tree
        r->data = minNode->data;
        delete minNode;
        return;
    }
    delete r;
}

我的 findMinNode 方法:

binarySearchTree::node * & binarySearchTree::findMinNode(node * r)
{
    if (r == NULL)      //if tree is empty
        return r;

    if (r->left == NULL && r->right == NULL)
        return r;
    else if (r->left != NULL)
        return findMinNode(r->left);
    else
        return findMinNode(r->right);
}

我的展示方式(使用前序遍历):

void binarySearchTree::display(node * r)
{
    if (r == NULL)
        return;

    display(r->left);
    cout << r->data << endl;
    display(r->right);
}

我正在使用公共(public) display() 方法，然后调用此私有(private) display(node * r) 方法。

我知道问题出在我使用 delete 时，因为当我单步执行代码并到达我的 display() 方法时，当它检查是否 r== NULL 在我刚刚删除的节点上，地址不是 NULL，地址为 0x000000000，而是 0x000000001。因此，我的程序会崩溃。我以前从未遇到过这个问题。任何帮助将不胜感激。

我应该补充一点，我按以下确切顺序插入了这些值:10、5、34、2、8、12、25、6、18、27、38、11。我试图删除值为 12 的节点因为它有两个 child 。

Answer 1

当您删除一个节点时，您需要将指向它的指针清零，在您的示例中，该指针可以是根节点、上一个->左节点或上一个->右节点。如果您将 previous 更改为 node ** 并让它指向 previous 指针(初始化为 &root)，那么您可以只说 *previous = null 或 *previous = r->right.