算法 8.6.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 8.6
void Delete_BST (BiTree &T,  KeyType kval ) {
      // 若二叉查找树T中存在关键字等于kval的数据元素，则删除之。
      f = NULL;
      if (Search_BST(T,kval,p,f)) {      // 找到其关键字等于kval的数据元素
        if (p->lchild && p->rchild) {    // 左右子树均不空
           q = p;  s = p->lchild;
           while (s->rchild) { q = s;  s = s->rchild; }
           p->data = s->data;            // s指向左子树中关键字最大的结点
           if (q != p )  q->rchild = s->lchild;             
           else  q->lchild = s->lchild;  // s结点即为p结点的左子树根
           delete s;    
        }// if
        else {
          if (!p->rchild) {              // 右子树空则只需挂接它的左子树
             q = p;  p = p->lchild; 
          }//if 
          else {                        // 左子树空，只需挂接它的右子树
            q = p;  p = p->rchild;  
          }
          // 将指针p所指子树挂接到被删结点的双亲(指针f所指的)结点上
          if (!f) T = p;                // 被删结点为根结点
          else  if (q == f->lchild)  f->lchild = p; 
                else  f->rchild = p;    // 完成子树的挂接
          delete q;                     // 释放被删结点空间
        }//else
      }//if
}//Delete_BST