二叉排序树

#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node{
    datatype key;
    struct node* lchild,*rchild;
}bsnode;
typedef bsnode *bstree;
void inserttree(bstree* t,datatype x){
    bstree f=NULL,p;
    p=*t;
    while(p){
        if(x==p->key) return;
        f=p;
        p=(x<p->key)?p->lchild:p->rchild;
    }
    p=(bstree)malloc(sizeof(bsnode));
    p->key=x;
    p->lchild=p->rchild=NULL;
    if(*t==NULL) *t=p;
    else {
        if(x<f->key) f->lchild=p;
        else f->rchild=p;
    }
}
bstree creattree(){
       bstree t=NULL;
       datatype x;
       printf("请输入一个以-1为结束标记的结点序列：\n");
       scanf("%d",&x);
       while(x!=-1){
           inserttree(&t,x);
           scanf("%d",&x);
       }
       return t;
}
void bssearch1(bstree t,datatype x,bstree *f,bstree *p)
{
    *f=NULL;
    *p=t;
    while(*p){
        if(x==(*p)->key) return;
        *f=*p;
        *p=(x<(*p)->key)?(*p)->lchild:(*p)->rchild;
    }
    return;
}//检索
bstree bssearch2(bstree t,datatype x){
    if(t==NULL||t->key==x)
        return t;
    if(x<t->key) return bssearch2(t->lchild,x);
    else return bssearch2(t->rchild,x);
}//检索
bstree delebstree(bstree t,datatype x){
    bstree pre,p,child;
    bssearch1(t,x,&pre,&p);
    if(p){
        //被删除的结点为叶子结点
        if(p->lchild==NULL&&p->rchild==NULL){
            if(pre){
                if(pre->lchild==p) pre->lchild=NULL;
            else pre->rchild=NULL;
            }
            else t=NULL;//删除树根
            free(p);
        }
        else{
            //被删除的结点左子树为空
            if(p->lchild==NULL&&p->rchild){
                if(pre){
                    if(pre->lchild==p) pre->lchild=p->rchild;
                    else pre->rchild=p->rchild;

                }
                else t=p->rchild;
                free(p);
            }
           else if(p->rchild==NULL&&p->lchild){
                if(pre){
                    if(pre->lchild==p) pre->lchild=p->lchild;
                    else pre->rchild=p->lchild;
                }
                else t=p->lchild;
                free(p);
            }
            else if(p->lchild!=NULL&&p->rchild!=NULL){
                child=p->rchild;
                while(child->lchild)
                  child=child->lchild;
                child->lchild=p->lchild;
                if(pre){//不是根节点
                     if(pre->lchild==p) pre->lchild=p->rchild;
                     else pre->rchild=p->rchild;
                }
                else t=p->rchild;//删除的是根节点
                free(p);
            }
        }
    }
    return t;
}
void print(bstree t){
    if(t){
        print(t->lchild);
        printf("%d ",t->key);
        print(t->rchild);
    }
}
int main(){
    bstree tree;
    tree=creattree();
    print(tree);
    printf("\n请输入待删除的结点:\n");
    datatype x;
    scanf("%d",&x);
    tree=delebstree(tree,x);
    print(tree);
}