C++从BST中删除一个节点

我遇到了我的删除功能问题。我不知道什么似乎是问题。请帮我解决这个问题。非常感谢你。C++从BST中删除一个节点

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; 
}

来源

2013-03-13 Alee Ciaral Policarpio

它应该做什么？它实际上做了什么？你有什么试图解决它？ – 2013-03-13 13:10:47

是的。我已经尝试解决它。我一整天都在努力。它实际上只需要从树中删除一个节点。 – 2013-03-13 13:17:03

所有其他功能都很好，除了tree_delete :(。 – 2013-03-13 13:18:59

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

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)

的逻辑需要冷凝 - 检查出约BST一些职位上的SO，赞一个：

Binary Search Tree Implementation

来源

2013-03-13 13:22:23 assem

C++从BST中删除一个节点

回答

相关问题