8.6.3　二叉排序树删除操作

8.6.3　二叉排序树删除操作

俗话说“请神容易送神难”，我们已经介绍了二叉排序树的查找与插入算法，但是对于二叉排序树的删除，就不是那么容易，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。

如果需要查找并删除如37、51、73、93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响，如图8-6-8所示。

图8-6-8

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如图8-6-9，就是先删除35和99结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。

图8-6-9

但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？比如图8-6-10中的47结点若要删除了，它的两儿子以及子孙们怎么办呢？

图8-6-10

起初的想法，我们当47结点只有一个左子树，那么做法和一个左子树的操作一样，让35及它之下的结点成为58的左子树，然后再对47的右子树所有结点进行插入操作，如图8-6-11所示。这是比较简单的想法，可是47的右子树有子孙共5个结点，这么做效率不高且不说，还会导致整个二叉排序树结构发生很大的变化，有可能会增加树的高度。增加高度可不是个好事，这我们待会再说，总之这个想法不太好。

图8-6-11

我们仔细观察一下，47的两个子树中能否找出一个结点可以代替47呢？果然有，37或者48都可以代替47，此时在删除47后，整个二叉排序树并没有发生什么本质的改变。

为什么是37和48？对的，它们正好是二叉排序树中比它小或比它大的最接近47的两个数。也就是说，如果我们对这棵二叉排序树进行中序遍历，得到的序列{29,35,36,37,47,48,49,50,51,56,58,62,73,88,93,99}，它们正好是47的前驱和后继。

因此，比较好的办法就是，找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s，如图8-6-12所示。

图8-6-12

根据我们对删除结点三种情况的分析：

叶子结点；
仅有左或右子树的结点；
左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除。

/* 若二叉排序树T中存在关键字等于key的数据元素
   时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE */
Status DeleteBST(BiTree *T, int key)
{
    /* 不存在关键字等于key的数据元素 */
    if (!*T)                      
        return FALSE;
    else
    {
        /* 找到关键字等于key的数据元素 */
        if (key == (*T)->data)    
            return Delete(T);
        else if (key < (*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}

这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第8行，此时执行的是Delete方法，对当前结点进行删除操作。我们来看Delete的代码。

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
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;
        }
        /* s指向被删结点的直接前驱 */
        (*p)->data = s->data;         
        if (q != *p)
            /* 重接q的右子树 */
            q->rchild = s->lchild;    
        else
            /* 重接q的左子树 */
            q->lchild = s->lchild;    
        free(s);
    }
    return TRUE;
}