c++ - 删除 BST 中有两个 child 的节点

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
}

那么这个item根本就没有child了，只需要将parent中的指针设置为nullptr即可。如果 iem 有一个 child ，您只需执行直通。

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

如果节点有 child ，那就更棘手了

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

这里是对这里发生的事情的图形解释:

你在这 !