#include <iostream.h>
#include <stdlib.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define NULL 0
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef struct{
int key;
}ElemType;
typedef struct BSTNode{
ElemType data;
struct BSTNode *lchild, *rchild;
}BSTNode,*BSTree;
int InitBST(BSTree &T){
if(!(T=(BSTree)malloc(sizeof(BSTNode))))exit(OVERFLOW);
T->data.key=NULL;
T->lchild=NULL;
T->rchild=NULL;
return OK;
}
int SearchBST(BSTree T,int key,BSTree f,BSTree &p){
if(!T){p=f;return FALSE;}
else if EQ(key,T->data.key){p=T;return TRUE;}
else if LT(key,T->data.key) return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
int InsertBST(BSTree &T,ElemType e){
BSTree p;
if(!SearchBST(T,e.key,NULL,p)){
BSTree s;
s=(BSTree)malloc(sizeof(BSTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if LT(e.key,p->data.key)
p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}
void TraverseBST(BSTree T){
if(T){
TraverseBST(T->lchild);
cout<<T->data.key<<'\t';
TraverseBST(T->rchild);
}
}
void main(){
BSTree T;
ElemType e;
int select;
do{
cout<<"1、建立空二叉排序树"<<endl;
cout<<"2、插入元素"<<endl;
cout<<"3、遍历二叉排序树"<<endl;
cout<<"0、退出"<<endl;
cout<<"请输入选项（0—3）："<<endl;
cin>>select;
switch(select){
case 0:break;
case 1:if(InitBST(T))
cout<<"成功建立空二叉排序树"<<endl;
break;
case 2:
cout<<"输入各元素："<<endl;
while(e.key!=0){
cin>>e.key;
InsertBST(T,e);
}
break;
case 3:cout<<"中序遍历二叉排序树"<<endl;
TraverseBST(T);
break;
}
}while(select);
}
