t_dele.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/**********************************************/
/*      基于二叉排序树的结点删除算法          */
/*   文件名：t_dele.c  函数名：delbstree()    */
/**********************************************/
bstree delbstree(bstree t,datatype x)
 { /*在二叉排序树t中删除结点值为x的结点*/
   bstree p,q,child;
   bssearch1(t,x,&p,&q);    /*查找被删结点*/
   if (q)              /*找到了待删除结点*/
    { 
    if (q->lchild==NULL && q->rchild==NULL)  /*情况1，被删结点为叶结点*/
       {  if (p)             /*待删除结点有双亲*/
             { if (p->lchild==q) p->lchild=NULL; else p->rchild=NULL;}
               else t=NULL;  /*被删结点为树根*/
          free (q);
        }
     else 
      if (q->lchild==NULL)  /*情况2，被删结点的左子树为空，用被删结点的右子树替代该结点*/
          { if (p)   /*被删结点的双亲结点不为空*/
             { if (p->lchild==q) 
                 p->lchild=q->rchild;             /*q是其双亲结点的左儿子*/
                       else p->rchild=q->rchild;  /*q是其双亲结点的右儿子*/
	     } else t=q->rchild;
            free(q);
           }
     else 
       if (q->rchild==NULL)/*情况3，被删结点的右子树为空，用被删结点的左子树替代该结点*/
          {  if (p)    /*被删结点的双亲结点不为空*/
              {if (p->lchild==q) 
                  p->lchild=q->lchild;             /*q是其双亲结点的左儿子*/
                        else p->lchild=q->lchild;  /*q是其双亲结点的右儿子*/
              } else t=q->lchild;
            free(q);
             }
        else   /*情况4， 被删结点的左右子树均不为空，用右子树代替被删结点，同时将被删结点的左子树
                  收为右子树中序首点的左儿子*/
            {    child=q->rchild;
                 while (child->lchild)     /*找被删结点右子树中的中序首点*/
                     child=child->lchild;
                 child->lchild=q->lchild;  /*收被删结点的左子树收为child的左孩子*/
                 if (p)                    /*被删结点不是树根*/
                   { if (p->lchild==q)
                       p->lchild=q->rchild;
                          else p->rchild=q->rchild;
                   } else t=q->rchild;    /*被删结点为树根*/
                 free(q);
             }
      }
   return t;
}