在BST中删除一个带有两个子节点的节点

Question

我试图实现一个二叉搜索树，并且我有一个节点删除问题。我做了一些测试，我认为我的功能唯一的问题是这种情况下，要删除的节点有两个孩子。我似乎在参考文献中的某处出现了混乱。这似乎是一个简单的问题，但我一直试图自己修复它太久

struct node 
{ 
    int val; 
    struct node *l; 
    struct node *r; 
}*Head=NULL; 

void del_x(struct node *&k,int x) 
{ 
    struct node *tmp,*tmp2,*rem; 
    if (k==NULL) return; 
    if (x > k->val) {if(k->r==NULL)return;else del_x(k->r,x);} 
    if (x < k->val) {if(k->l==NULL)return;else del_x(k->l,x);} 
    if (x == k->val) 
    { 
     tmp=k; 
     if (k->l==NULL && k->r==NULL) {tmp=k->l;k=tmp;delete tmp;return;}//no children 
     else if (k->l==NULL) {tmp=k->r;k=tmp;return;}//one child on the left 
     else if (k->r==NULL) {tmp=k->l;k=tmp;return;}//one child on the right 
     else //two children <-I think the problem lies in this else 
     { 
      rem=k; 
      tmp=k->r; //go to right subtree 
      while(tmp->l!=NULL) {tmp2=tmp;tmp=tmp->l;} //search minimum 
      tmp2->l=NULL; 
      k=tmp; 
      rem->val=tmp->val; 
      k=rem; 
      return; 
     } 
    } 
} 

Answer 1

有几个问题。

首先，无论如何，如果达到x==k->val的条件，这是真的，你会总是需要删除当前由k指向的节点。

if (x == k->val) 
{ 
    tmp=k;  // keep track of the node to delete 
    ...   // update k but don't return (and don't change tmp) 
    delete tmp; // get rid of the deleted node for good 
} 

然后该项目根本没有任何子项，您只需要将父指针设置为nullptr。如果艾姆有一个孩子，那么你只需要做一个传球。

if (k->l==nullptr && k->r==nullptr) 
     k=nullptr; 
    else if (k->l==nullptr) 
     k=k->r; 
    else if (k->r==nullptr) 
     k=k->l; 
    else { //two children 
     ... 
    } 

如果节点有孩子，这是更棘手

else { //two children 
     k=k->l; // take the left subtree 
     for (rem=k; rem->r!=nullptr; rem=rem->r) 
      ;  // find the end of its right subtree 
     rem->r = tmp->r; // append the right subtree at its end. 
    } 

这里的东西在这里发生的图形解释：

你来了！