如何删除特定节点是二叉搜索树？

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有问题。在访问过时的节点之前，代码很可能会出错。