16.二叉排序树

/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode                        //结点结构
{
    int data;                                            //结点数据
    Struct BiTNode *lchild,*rchild;       //左右孩子指针
}BiTNode,*BiTree;   

/*递归查找二叉排序树T中是否存在key,
   * 指针f指向T的双亲，其初始调用值为NULL
    *若查找成功，则指针p指向该数据元素结点，并返回TRUE；否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
    if(!T)                            //查找不成功(为空树)
    {
            *p=f;
            return FALSE;
    }
    else if(key==T->data)  //查找成功
    {
            *p=T;
            return TRUE;
    }
    else if(key<T->data)
            return SearchBST(T->lchild,key,T,p);        //在左子树继续查找
    else
            return SearchBST(T->rchild,key,T,p);        //在右子树继续查找  
}

/*当二叉排序树T中不存在关键字等于key的数据元素时，
 *    插入key并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree *T,int key)
{
    BiTree p,s;
    /*调用查找函数查找是否存在该关键字*/
    //a.若查找不成功
    if(!SearchBST(*T,key,NULL,&p))    
    {
          s=(BiTree)malloc(sizeof(BiTNode));    //为结点s开辟一段内存空间
          s->data=key;                                       //将关键字存放到s指向结点的数据域中
          s->lchid=s->rchild=NULL;                //初始化结点s的左右指针域
         if(!p)
                *T=s;                //插入s为新的根结点
         else if(key<p->data)//若关键字小于p结点数据值，插入s为结点p的左孩子
                p->lchild = s;   
          else                        //若关键字大于p结点数据值，插入s为结点p的右孩子
                p->rchild=s;   
    }
    /*树中已有关键字相同的结点，不再插入*/
    else
    {
            return FALSE;    
    }
}

/*假如有一个数据集={62,88,58,47,35,73,51,99,37,93}
    * 构建一个二叉排序树*/
int i;
int a[0]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
    InsertBST(&T,a[i]);
}

Status DeleteBST(BiTree *T,int key)
{
     if(!*T)    //不存在关键字等于key的数据元素
            return FALSE;
    else
    {
        if(key==(*T)->data)    //找到关键字等于key的数据元素
                return Delete(T);    //调用Delete函数删除该结点
        else if(key<(*T)->data)
                return DeleteBST(&(*T)->lchild,key);    
        else
                return DeleteBST(&(*T)->rchild,key);
    }   
}

/*从二叉排序树中删除结点p,并重接它的左或右子树*/
Status Delete(BiTree *p)
{
     BiTree q,s;
    /*情况二：删除结点p的右子树或左子树为空*/
    if((*p)->lchild==NULL)               //a.右子树空则只需重接它的左子树
    {
            q=*p;    *p=(*p)->lchild;    free(q);
    }    
    else if((*p)->rchild==NULL)        //b.只需重接它的右子树
    {
            q=*p;    *p=(*p)->rchild;    free(q);    //将指针p指向的结点
    }
    //情况三：左右子树均不为空
    else
    {
            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;    //重接q的右子树
            else
                    q->lchild=s->lchild;    //重接q的左子树
            free(s);
    }
    return TRUE;
}