Question

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

如果需要查找并删除如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;
}

1．程序开始执行，代码第4～7行目的是为了删除没有右子树只有左子树的结点。此时只需将此结点的左孩子替换它自己，然后释放此结点内存，就等于删除了。

2．代码第8～11行是同样的道理处理只有右子树没有左子树的结点删除问题。

3．第12～25行处理复杂的左右子树均存在的问题。

4．第14行，将要删除的结点p赋值给临时的变量q，再将p的左孩子p->lchild赋值给临时的变量s。此时q指向47结点，s指向35结点，如图8-6-13所示。

图8-6-13

5．第15～18行，循环找到左子树的右结点，直到右侧尽头。就当前例子来说就是让q指向35，而s指向了37这个再没有右子树的结点，如图8-6-14所示。

图8-6-14

6．第19行，此时让要删除的结点p的位置的数据被赋值为s->data，即让p->data=37，如图8-6-15所示。

图8-6-15

7．第20～23行，如果p和q指向不同，则将s->lchild赋值给q->rchild，否则就是将s->lchild赋值给q->lchild。显然这个例子p不等于q，将s->lchild指向的36赋值给q->rchild，也就是让q->rchild指向36结点，如图8-6-16所示。

图8-6-16

8．第24行，free(s)，就非常好理解了，将37结点删除，如图8-6-17所示。

图8-6-17

从这段代码也可以看出，我们其实是在找删除结点的前驱结点替换的方法，对于用后继结点来替换，方法上是一样的。