二叉排序树的删除操作

先来看这个二叉排序树

下面是讨论删除的情况：

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

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

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

也就是说，比如要删除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;
}