#include<stdio.h>
#include<stdlib.h>
typedef struct Bitree
{
    int key;
    struct Bitree *lchild,*rchild;
}Bitnode,*Bitree;
bool Search(Bitree T,int key,Bitree f,Bitree *p)
{
    if(T==NULL)
    {
        *p=f;
        return false;
    }
    else if(key==T->key)
        {
            *p=T;
            return true;
        }
        else if(key<T->key)
            {
                Search(T->lchild,key,T,p);
            }
        else
            Search(T->rchild,key,T,p);
}
void CreateTree(Bitree *T,int n)
{
    int i,index;
    Bitree p,s;
    printf("请输入排序二叉树的关键字序列:");
    for(i=1;i<=n;i++)
    {

        scanf("%d",&index);
        if(!Search(*T,index,NULL,&p))
        {
            s=(Bitree)malloc(sizeof(Bitnode));
            s->key=index;
            s->lchild=NULL;
            s->rchild=NULL;
            if(!p)
                *T=s;
            else
                if(index<p->key)
                p->lchild=s;
            else
                p->rchild=s;
        }
    }
}
void VisitBitree(Bitree T)
{
    if(T)
    {
        VisitBitree(T->lchild);
        printf("%d->",T->key);
        VisitBitree(T->rchild);
    }

}
void Delete(Bitree &p)
{

    Bitree q,s;
    if(!p->rchild)
    {
        q=p;
        p=p->lchild;
        free(q);
    }
    if(!p->lchild)
    {
        q=p;
        p=p->rchild;
        free(q);
    }
    else
    {
        q=p;
        s=p->lchild;
        while(s->rchild)
        {
            q=s;
            s=s->lchild;
        }
        p->key=s->key;
        if(q!=p)
        {
           q->rchild=s->lchild;
        }
        else
            q->lchild=s->lchild;
    }
}
bool DeleteB(Bitree *T,int x)
{
    if(!T)
        return false;
    else
    {
        if(x==T->key)
        {
            Delete(T);
            return true;
        }
        else if(x<T->key)
            DeleteB(T->lchild,x);
        else
            DeleteB(T->rchild,x);
    }
}
int main()
{
    int n,x;
    Bitree T=NULL;
    printf("请输入排序树序列元素个数:\n");
    scanf("%d",&n);
    CreateTree(&T,n);

    printf("排序树序列中根访问序列:\n");
    VisitBitree(T);
    printf("\n");

    printf("输入你要删除的元素:");
    scanf("%d",&x);
    if(DeleteB(T,x))
    {
        printf("排序树修改后的序列中根访问序列如下:\n");
        VisitBitree(T);
        printf("\n");

    }
    else
        printf("删除失败！该元素不在序列中\n");
}