c++ - 在二叉搜索树 C++ 中删除(树不会更新)和堆损坏

Question

我正在尝试为二叉树编写节点删除。这些是我的节点和树结构:

class node{
public:
    int value;
    node* left;
    node* right;
    ~node();
};

class tree{
public:
    node* root;
    ....
};

这是我写的函数:

void tree::del(node** r, int x){
if(*r)
{
    if((*r)->value==x)
    {
        if(!(*r)->left)
            *r= (*r)->right;
        else if(!(*r)->right)
            *r= (*r)->left;
        else 
        {
            int k= delMax((*r)->left);
            (*r)->value= k;
        }
    }
    else if((*r)->value > x)
    {
        node* k= (*r)->left;
        del(&k, x);
    }
    else
    {
        node* k= (*r)->right;
        del(&k, x);
    }
}}

我的问题是，一旦我到达所需的元素，指针就会改变，但是当树被递归重建时，它会回到原来的状态，并且没有元素被删除。我认为将指针传递给指针可以解决这个问题，但事实并非如此。 delMax 从树中删除最大元素，它自己可以正常工作。

另外，在最后两个类的析构函数中，我应该如何放置删除？因为如果我只是把删除权；删除左边；在 ~node() 中删除 root in ~tree() 我得到一个错误，我正在破坏堆。

谢谢!

Answer 1

通过创建局部变量k 并传递它的 地址，通过*r 的赋值影响局部变量而不是任何指针在树上。

顺便说一句，编写 node *&r 可能会为您节省几个 & 和 *。