#include<stdio.h>
#include<stdlib.h>
typedef struct node{
 int data;//节点信息
 struct node *lchild;//左孩子
 struct node *rchild;//右孩子
 }bitnode;

void cre(bitnode **w);
bitnode *InsertBST(bitnode *b,int m);
void zhongxu(bitnode *T);//中序遍历
void del(bitnode *b,int m);

void  cre(bitnode **w)
{
 
 int n,i;
 int a[10];
 printf("Enter the node of number: ");
 scanf("%d",&n);
 
 for(i=0;i<n;i++){    //输入树的结点个数
  printf("Enter the %d integer: ",i+1);
  scanf("%d",&a[i]);
  if(*w==NULL)
    *w=InsertBST(*w,a[i]);
  else
    InsertBST(*w,a[i]);
 }
  
}
bitnode *InsertBST(bitnode *b,int m)
{
 bitnode *p;
 if(b==NULL)
 {
  b=(bitnode *)malloc(sizeof(bitnode));
  b->data=m;
  b->lchild=b->rchild=NULL;
  return b;
 }
 else
 {
  if(m<b->data)
  {
   if(b->lchild!=NULL && m>b->lchild->data)
   {
    p=(bitnode *)malloc(sizeof(bitnode));
    p->data=m;
    p->rchild=NULL;
    p->lchild=b->lchild;
    b->lchild=p;
   }
   else
       InsertBST(b->lchild,m);
  }
  else if(m>b->data)
  {
   if(b->rchild!=NULL && m<b->rchild->data)
   {
    p=(bitnode *)malloc(sizeof(bitnode));
    p->data=m;
    p->lchild=NULL;
    p->rchild=b->rchild;
    b->rchild=p;
   }
   else
       InsertBST(b->rchild,m);
  }
 
 }
}

void zhongxu(bitnode *T)//中序遍历
{
 if(T!=NULL)
 {
   zhongxu(T->lchild);
   printf("%d ",T->data);
   zhongxu(T->rchild);
 }
}

void del(bitnode *b,int m)
{
 bitnode *q,*s;
 if(b->data==m){
  q=b;
  s=q->lchild;
  while(s->rchild){
   q=s;
   s=s->rchild;
  }
  b->data=s->data;
  if(q!=b)
   q->rchild=s->lchild;
  else
   q->lchild=s->lchild;
  free(s);
 }
 else
 {
  if(m<b->data)
    del(b->lchild,m);
  else if(m>b->data)
    del(b->rchild,m);
  else
   printf("No Found! ");
 }
}

main()
{
 bitnode *b=NULL;
 int m,x;
 printf("*******************************\n\n");
 printf("***********0:退出程序**********\n");
 printf("***********1:建立结构**********\n");
 printf("***********2:插入整数**********\n");
 printf("***********3:中序输出**********\n");
 printf("***********4:删除节点**********\n");
 do{
 // printf("\n\n");
  printf("请选择: ");
  scanf("%d",&x);
  switch(x){
   case 0:
    break;
   case 1:
    cre(&b);break;
   case 2:
    printf("请输入整数: ");
    scanf("%d",&m);
    InsertBST(b,m);
    break;
   case 3:
    zhongxu(b);
    break;
   case 4:
       printf("Enter the integer: ");
       scanf("%d",&m);
        del(b,m);
        break;
   default:
    printf("输入错误!");
    break;
  }
 }while(x!=0);
 return 0;
}