#include<stdio.h>
#include<stdlib.h>
#define  MAXSIZE 100
#define OK 1
#define FALSE 0
#define  ElemType int

typedef  struct BSTNode
{
	ElemType data;
	struct BSTNode * lchild,* rchild;
}BSTNode,* BSTree;

int ElemList[MAXSIZE+1];

BSTree root=NULL;

void Init(int num)/*初始化*/
{
	ElemList[0]=num;
}

int EQ(int key,int data)
{
	if(key==data)
		return OK;
	else
		return FALSE;
}

int LT(int key,int data)
{
	if(key<data)
		return OK;
	else
		return FALSE;
}

int SearchBST(BSTree T, ElemType key,BSTree f,BSTree & p )
{
	 if(!T)
	 {
		 p=f;
		 return FALSE;
	 }
	 else if(EQ(key,T->data))
	 {
		 p=T;
		 return OK;
	 }
	 else if(LT(key,T->data))
		 SearchBST(T->lchild,key,T,p);
	 else
		 SearchBST(T->rchild,key,T,p);

}

int InsertBST(BSTree &T,ElemType e);

BSTree CreatBST(BSTree &T)
{
	int i;
	if(ElemList[0]==0)
		return NULL;
	else
	{
		for(i=1;i<=ElemList[0];i++)
		{
			InsertBST(T,ElemList[i]);
		}
	}
	return T;
}

int Delete(BSTree & p)
{
    BSTree q,s;
	if(!p->rchild)
	{
		q=p;
		p=p->lchild;
		free(q);
	}else if(!p->lchild)
	{
		q=p;
		p=p->rchild;
		free(q);
	}
	else{
		q=p;
		s=p->lchild;
		while(s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		p->data=s->data;
		if(q!=p)
			q->rchild=s->lchild;
		else
			q->lchild=s->lchild;
		delete s;
	}
	return OK;
}



int DeleteBST(BSTree & T,ElemType key )
{
	if(!T)
		return FALSE;
	else
	{
		if(EQ(key,T->data))
		{
			Delete(T);
			return OK;
		}
		else if(LT(key,T->data))
			 DeleteBST(T->lchild,key);
		else
			 DeleteBST(T->rchild,key);
		return OK;
	}
}



int InsertBST(BSTree &T,ElemType e)
{
	BSTree s,p=NULL;
	if(!SearchBST(T,e,NULL,p))
	{
		s=(BSTree)malloc(sizeof(BSTNode));
	if(!s)
		return FALSE;
	s->data=e;
	s->lchild=s->rchild=NULL;
	if(!p)
		T=s;
	else if (LT(e,p->data))
		p->lchild=s;
	else
		p->rchild=s;
	return OK;
	}
	else return FALSE;
} 

void JudgeBST(ElemType data)
{
    BSTree p;
	if(SearchBST(root,data,NULL,p ))
		printf("含有所需要的數字\n");
	else
		printf("不含有所查找的數字\n");
}

void ClearBST(BSTree &T)
{
	if(!T)
		return ;
	else if(T->lchild==NULL&&T->rchild==NULL)
	{
		free(T);
		return ;
	}
	else
	{
		ClearBST(T->lchild);
		ClearBST(T->rchild);
		free(T);
	}

}
void TraverseBiTree(BSTree T)
{
	if(T)
	{
		TraverseBiTree(T->lchild);
		printf("%4d",T->data);
        TraverseBiTree(T->rchild);
	}
}
void main()
{
	int num,i,temp,choice;
	printf("請輸入元素的個數\n");
	scanf("%d",&num);
	Init(num);
	printf("請輸入元素\n");
	for(i=1;i<=num;i++)
		scanf("%d",&ElemList[i]);
	root=CreatBST(root);
	printf("*******************\n");
	TraverseBiTree(root);
	printf("\n");
	printf("*******************\n");
	do{
	printf("1插入一個元素 2 刪除一個元素3 查找的整數 4 輸出所有元素 else 退出\n");
	scanf("%d",&choice);
    if(choice==1)
	{
    printf("請輸入插入元素\n");
    scanf("%d",&temp);
    InsertBST(root,temp);
    printf("****成功*****\n");
	}
	else if(choice==2)
	{
	printf("請輸入刪除元素\n");
	scanf("%d",&temp);
	DeleteBST(root,temp );
    printf("****刪除成功****\n");
    }
	else if(choice==3)
	{
    printf("請輸入查找元素\n");
    scanf("%d",&temp);
    JudgeBST(temp);
	}
	else if(choice==4)
	{
	 printf("*******************\n");
     TraverseBiTree(root);
	 printf("\n");
	 printf("*******************\n");
	}
	}while(choice==1||choice==2||choice==3||choice==4);
	ClearBST(root);
	printf("已經全部清空\n");
	
}