#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;
typedef struct node
{ElemType data;
struct node *lch,*rch;
}Snode;
Snode *creat_bt();
Snode *insert1(Snode *t,Snode *s);
Snode *insert2(Snode *t,Snode *s);
void inorder(Snode *p);

Snode *p,*q,*t,*f;
void main()
{Snode *H;int k;char ch;
do{printf("\n\n\n");
   printf("\n 1.建立二叉排序树 ");
   printf("\n 2.中序递归遍历二叉树 ");
   printf("\n 3.中序非递归遍历二叉树");
   printf("\n 4.结束程序");
   printf("\n=============================");
   printf("\n  (1,2,3,4,5,6):"); scanf("%d",&k);
   switch(k)
   {case 1:{H=creat_bt();
   }break;
    case 2:{printf("\n 中序递归遍历输出:"); inorder(H);
          }break;
    case 3:{printf("\n 中序非递归遍历输出:"); inorder(H);
           }break;
    case 4:{printf("\n 删除结点"); void delet(Snode *t,Snode *p,Snode *f);;
           }break;
    case 6:exit(0);
   }
}while(k>0&&k<=6);
printf("\n   再见! "); scanf("%c",&ch);
}
Snode *creat_bt()
{Snode *t0,*s; int n,i; ElemType k;
printf("\n n="); scanf("%d",&n);
t0=NULL;
for(i=1;i<=n;i++)
{printf("\n %d key=",i);scanf("%d",&k);
  s=(Snode*)malloc(sizeof(Snode));
  s->data=k;s->lch=NULL;s->rch=NULL;
  t0=insert1(t0,s);
}
return(t0);
}
Snode *insert1(Snode *t,Snode *s)
{if(t==NULL) t=s;
else
if(s->data<t->data)
    t->lch=insert1(t->lch,s);
else t->rch=insert1(t->rch,s);
return(t);
}
Snode *insert2(Snode *t,Snode *s)
{
if(t==NULL)t=s;
else{p=t;
while(p!=NULL)
       {q=p;
       if(s->data<p->data) p=p->lch;
            else p=p->rch;
       }
       if(s->data<q->data) q->lch=s;
         else q->rch=s;
}
return(t);
}
void inorder(Snode *p)
{
if(p!=NULL){inorder(p->lch);
             printf("%8d",p->data);
             inorder(p->rch);
}

void delet(Snode *t,Snode *p,Snode *f)
{
bool=1;
Snode *s,*q;
if(p->lch==NULL)s=p->lch;
else if(p->rch==NULL)s=p->lch;
else{q=p;s=p->rch;    /*p左、右孩子均不空的情况*/
while(s->lch!=NULL){q=s;s=s->lch;}
/*上述语句是查找p结点右子树的最左结点*/
if(q==p)q->rch=s->rch;
else q->lch=s->rch;
p->data=s->data;
free(s); bool=0;   /*删除完成*/
}
if(bool==1)       /*p不是有左、右两个孩子的情况*/
{if(f==NULL)t=s; /*f==NULL即是p就是根t情况*/.

else if(f->lch==p)f->lch=s; else f->rch=s;
free(p);
}
}
}