二叉排序树的删除操作-ag真人游戏

先来看这个二叉排序树

下面是讨论删除的情况：

我们知道，如果要删除的叶子结点，则可以直接删除。

但如果删除的不是叶子结点呢？

我们知道这个树的中序遍历如下：

也就是说，比如要删除105，则我们可以把104，或108提上去覆盖掉，这样实现了删除，又不保证了他是二叉排序树。

下面是代码

status deletebst(bitree *t, int key)
{
    if( !*t )
    {
        return false;
    }
    else
    {
        if( key == (*t)->data )
        {
            return delete(t);
        }
        else if( key < (*t)->data )
        {
            return deletebst(&(*t)->lchild, key);
        }
        else
        {
            return deletebst(&(*t)->rchild, key);
        }
    }
}
status delete(bitree *p)
{
    bitree q, s;
    
    if( (*p)->rchild == null )
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else if( (*p)->lchild == null )
    {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else
    {
        q = *p;
        s = (*p)->lchild;
        
        while( s->rchild )
        {
            q = s;
            s = s->rchild;
        }
        
        (*p)->data = s->data;
        
        if( q != *p )
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        
        free(s);
    }
    
    return true;
}