#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct{
    ElemType key;
}KeyType;   //元素類型
typedef struct node
{KeyType data;
 struct node *lch,*rch;
}Snode,*BiTree;
Snode *creat_bt();
Snode *insertl(Snode *t,Snode *s);
void inorder(Snode *p);
BiTree find(BiTree root,ElemType key);
void Delete(Snode *H,ElemType key);
void main()
{Snode *H;int k;char ch;BiTree s;ElemType key;/*Snode T*/;
 do{printf("\n\n\n");
   printf("\n   1  建立二叉排序樹");
   printf("\n   2  中序遍歷二叉樹并查找給定結(jié)點的值是否存在");
   printf("\n   3  刪除二叉排序樹中的結(jié)點");
   printf("\n   4  結(jié)束程序運行"  );
   printf("\n===========================");
   printf("\n  請輸入你的選擇(1,2,3,4):");scanf("%d",&k);
   switch(k)
   {case 1:{H=creat_bt();}break;
    case 2:{printf("\n  中序遍歷輸出:");
	        inorder(H);
            printf("\n");
            do{    //二叉排序樹的查找，可多次查找，并輸出查找的結(jié)果
            printf("Input the key you want to search:");
            scanf("%4d",&key);
            s=find(H,key);
            if (s!=NULL) printf("success,the value is %4d ",s->data.key);
            else         printf("unsuccess");
            printf("\ncontinue?y:n\n");getchar();
            ch=getchar();
			}while(ch=='y'||ch=='Y');
		   }break;
	case 3:{printf("/n請輸入要刪除的數(shù)據(jù)：");
            scanf("%4d",&key);
            Delete(H,key);
            printf("刪除操作完畢。/n");}break;
    case 4:{ }break;
   }
}while(k!=4);
printf("\n      再見！       ");scanf("%d",&ch);
}
/*建立二叉排序樹*/
Snode *creat_bt()
{Snode *t0,*s;int n,i;KeyType 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=insertl(t0,s);          /*調(diào)用插入函數(shù)*/
 }
 return(t0);
}
/*在二叉排序樹t中，插入一個結(jié)點s的遞歸算法*/
Snode *insertl(Snode *t,Snode *s)
{if(t==NULL) t=s;
 else if(s->data.key<t->data.key)
 t->lch=insertl(t->lch,s);/*將s插入t的左子樹*/
 else t->rch=insertl(t->rch,s);/*將s插入t的右子樹*/
 return(t);
}
/*中根遍歷二叉樹*/
void inorder(Snode *p)
{if(p!=NULL)
{inorder(p->lch);
printf("%8d",p->data);
inorder(p->rch);
}
}
BiTree find(BiTree root,ElemType key){  //在二叉排序樹中查找其關(guān)鍵字等于給定值的結(jié)點是否存在，并輸出相應(yīng)信息
 Snode *p;
 p=root;
 if (p==NULL) return NULL;
    else if (p->data.key==key) return p;
    else if (key<p->data.key) return find(p->lch,key);
    else return find(p->rch,key);
}
void Delete(Snode *H,ElemType Key)
{Snode *parent=NULL, *p, *q,*child;
p=H;
while(p)
{if(p->data.key==Key) break;
parent=p;
p=(Key<p->data.key)?p->lch:p->rch;
}
if (!p) {printf("沒有找到要刪除的結(jié)點/n");return;}
q=p;
if (q->lch && q->rch)
for (parent=q,p=q->rch; p->lch; parent=p,p=p->lch);
child=(p->lch)?p->lch:p->rch;
if (!parent) H=child;
else {if (p==parent->lch)
parent->lch=child;
else parent->rch=child;
if (p!=q)
q->data.key=p->data.key;
}
free(p);
}