2000-d-五

btree * DeleteBST(btree *b, ElemType x)  
{  
      if (b)  
      {  
            if (b->data == x)  
                  b = DelNode(b);  
            else if (b->data > x)  
                  //注意此处的b->lchild、b->rchild 无此句，会出现删除后断链情况
                  b->lchild = DeleteBST(b->lchild, x); 
            else  
                  b->rchild = DeleteBST(b->rchild, x);  
      }  
      return b;  
}  

//删除结点，准确的说是调整数值，删除无用结点
btree * DelNode(btree *p)  
{  
      if (p->lchild)  
      {  
            btree *r = p->lchild;   //r指向其左子树;  
            btree *prer = p->lchild;   //prer指向其左子树;  
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r  
        {  
                  prer = r;  
            r = r->rchild;  
        }  
            p->data = r->data;  
  
        if(prer != r)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子  
                  prer->rchild = r->lchild;  
            else  
            p->lchild = r->lchild; //否则结点p的左子树指向r的左子树  
  
            free(r);  
            return p;  
      }  
      else  
      {  
            btree *q = p->rchild;   //q指向其右子树;  
            free(p);  
            return q;  
      }  
}