如何刪除特定節點是二叉搜索樹？

Question

我想刪除特定的節點，但我沒有看到問題出在哪裏。

其實，我通過Find()得到節點，然後用Remove()刪除它。

該程序崩潰，每當Delete()火災。

bool RemoveNode(int key) 
{ 
    if (IsEmpty()) 
     return false; 
    Node* r = Find(key,root); 
    if (r==nullptr) 
     return false; 
    return Remove(r); 
} 
bool Remove (Node* &r) 
{ 
    if (r->left==nullptr && r->right ==nullptr) 
    { 
     delete r; 
     r=nullptr; 
     return true; 
    } 
    if (r->left==nullptr) 
    { 
     Node* temp = r->right; 
     delete r; 
     r=nullptr; 
     r=temp; 
     return true; 
    } 
    if (r->right==nullptr) 
    { 
     Node* temp = r->left; 
     delete r; 
     r=nullptr; 
     r=temp; 
     return true; 
    } 
    Node* Max = FindMax(r->left); 
    r->data = Max->data; 
    Remove(Max); 

    return true; 
} 
Node* FindMax(Node* r) 
{ 
    if(r->right==nullptr) 
     return r; 
    return FindMax(r->right); 
} 
Node* Find(int key, Node* &r) 
{ 
    if (r==nullptr) 
     return nullptr; 

    if (r->data==key) 
     return r; 

    if (key < r->data) 
     return Find(key,r->left); 
    else 
     return Find(key,r->right); 
} 

Answer 1

顯然，你Remove()功能旨在修改指針節點，獨立於所在：不是傳遞的原始指針，你傳遞給指針的引用。這樣，您可以將樹的root指針，left或right更新爲下一個的組成部分。只要你將它傳遞給正確的參考，我認爲代碼應該工作。的Find()結果是一個指針，而不是相關的指針的引用：

可變r在Remove()這是在RemoveNode()定義的本地變量實際上修改。但是，您需要修改指向該節點的樹結構中的指針，而不是任意的局部變量。

的解決將是使用Find()' which correctly returns a reference to the pointer rather than the pointer itself. Your recursive查找（）would be up to the task if it returned a節點* & rather than a節點*`的一個特殊版本。由於你的樹似乎並不平衡，堆棧空間相對有限，所以我寧願使用非遞歸函數。取而代之的是參考返回一個指針，將維持一個指針的指針當前節點，而不是一個指向節點：

Node** InternFind(int key) { 
    Node** n = &this->root; 
    while (*n && (*n)->key != key) { 
     n = &(key < (*n)->key? (*n)->left: (*n)->right); 
    } 
    return n; 
} 

的代碼是未經測試，可能不完全正確。一旦你得到了指針品特，但是，你可以更新它無需處理，其中來自傳來：

Node** r = InternFind(key); 
if (*r) { 
    Remove(*r); 
    return true; 
} 
else { 
    return false; 
} 

雖然我不知道什麼是「如果Delete()火」的意思，我會想你對於同一個指針p重複使用delete p有問題。在訪問過時的節點之前，代碼很可能會出錯。