0

我的删除功能有问题。我不知道似乎是什么问题。请帮我解决这个问题。非常感谢您。

node* tree_minimum(node *x){

    while(x->left!=NULL){
        x=x->left;
    }
    return x;
}

node* tree_successor(node *x){

    if(x->right!=NULL)
        return tree_minimum(x->right);

    node *y;
    y=new node;
    y=x->parent;

    while(y!=NULL&&x==y->right){
        x=y;
        y=y->parent;
    }
    return y;
}

node* tree_search(node* x,int k){

    if(x==NULL||k==x->key)
        return x;

    if(k<x->key)
        return tree_search(x->left,k);
    else
        return tree_search(x->right,k);
}

node* tree_delete(int b){

    node *y;
    y=new node;
    node *x;
    x=new node;
    node *z;
    z=new node;

    z=tree_search(root,b);

    if(isempty()){
        cout<<"TREE is empty.";
        return NULL;
    }

    if(z->left==NULL||z->right==NULL)
        y=z;
    else
        y=tree_successor(z);

    if(y->left!=NULL)
        x=y->left;
    else
        x=y->right;

    if(x!=NULL)
        x->parent=y->parent;
    if(y->parent==NULL)
        root=x;
    else{

    if(y=y->parent->left)
        y->parent->left=x;
    else
        y->parent->right=x;
    }
    if(y!=z)
        y->key=z->key;

    return y;
}
4

1 回答 1

3

不幸的是，您在这里遇到了很多问题；我认为您误解了内存分配：

node *y;
y=new node;
y=x->parent;  // Holy Mackerel!

在第二行分配内存，将地址返回给新分配的内存；下一行更改了 y 指向的地址 (!!) - 丢失分配的内存位置并造成内存泄漏。由于这些分散在整个代码中，并且您没有main()显示调用或显示调用的代码 - 没有太多需要继续。

如果您只是复制指针，则不需要执行动态分配（即new运算符）。

int *x = new int;
int y = 2;
*x = 1;  // Assigns the memory (int) pointed to by x to 1
x = &y;  // Reassigns x to point to y - but without delete the allocated memory's last reference is lost

我真的建议你在继续之前先拿一本书。

编辑：还要注意以下条件：

if (y=y->parent->left)

当你最有可能的意思是：

if (y == y->parent->left)

逻辑需要浓缩 - 查看一些关于BSTSO 的帖子，比如这个：

二叉搜索树实现

于 2013-03-13T13:22:23.070 回答