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中刪除一個節點

回答

相關問題