#include<stdio.h>
#include<malloc.h>
#define OVERFLOW -2
#define OK 1
#define TURE 1
#define FALSE 0
#define Insert_Fail 0;
#define Insert_Success 1;
//對于數值型關鍵字
#define EQ(a,b) ((a)==(b)) 
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef struct     //查找表data類型
{
	int  key;      //關鍵字項
    char c;        //其它數據項
}TElemType;
typedef struct BiTNode 
{ 
   TElemType  data; 
   struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree;

//*1二叉排序樹的查找
int SearchBST(BiTree T,int key,BiTree f,BiTree *p)//T為根節點，f為p的父結點，p為查找到后返回的節點
{
	if(!T)               //T為空，查找失敗
	{
		(*p)=f;
		return FALSE;
	}
	else if(EQ(key,T->data.key))
	{
		(*p)=T;            //要查找的為根節點
		return TURE;
	}
	else if(LT(key,T->data.key))
		return SearchBST(T->lchild,key,T,p);    //在左子樹中繼續查找
	else
		return SearchBST(T->rchild,key,T,p);   //在右子樹中繼續查找
}
//*2二叉排序樹的插入
int InsertBST(BiTree *T,TElemType e) 
{
	BiTNode *s;
	int result;
	BiTree p;
	s=(BiTNode*)malloc(sizeof(BiTNode));
	s->data=e;   
	s->lchild=s->rchild=NULL;
    result=SearchBST(*T,e.key,NULL,&p); 
    if(result==TURE) return Insert_Fail;                     // 插入失敗  
    if(!p)   	(*T)=s;                                      // 插入 s 為新的根結點
      else if(LT(e.key,p->data.key))      p->lchild=s;       // 插入 *s 為 *p 的左孩子
	  else  p->rchild=s;                                     // 插入 *s 為 *p 的右孩子
	return Insert_Success;                                   // 插入成功
} // Insert BST
//3二叉排序樹的刪除
int Delete(BiTree *f, BiTree *p)//從二叉排序樹中刪除結點 p，重接它的左(右)子樹
{
	BiTree q,s;
	if(!((*p)->rchild)&&!((*p)->lchild)) 
    {  
		if((*f)->lchild==(*p)) (*f)->lchild=NULL;
        else (*f)->rchild=NULL;  
		free(*p);
	} 
    else if(!((*p)->rchild)) 
    {  
		if((*f)->lchild==(*p)) (*f)->lchild=(*p)->lchild;
          else 	(*f)->rchild=(*p)->lchild; 
		free(*p);
	} 
	else if(!((*p)->lchild)) 
    {  
		if((*f)->lchild==(*p)) 	(*f)->lchild=(*p)->rchild;
        else 	(*f)->rchild=(*p)->rchild; 
		free(*p);
	} 
	else                      // 左右子樹均不空
	{  
		q=*p;  
		s=(*p)->lchild;
		while(s->rchild)
		{ 
			q=s; 
			s=s->rchild;
		}                      // s 指向被刪結點的前驅
		(*p)->data=s->data;
		if(q!=*p)  q->rchild=s->lchild;
		else  q->lchild=s->lchild;
		free(s);
    }
	return TURE;
}
int DeleteBST(BiTree T,BiTree f,int key)
{
	if(!T)	return FALSE;
	else{
		if(EQ(key,T->data.key))
			return  Delete(&f,&T);
		else if(LT(key,T->data.key))
			return DeleteBST(T->lchild,T,key);
		else
			return DeleteBST(T->rchild,T,key);
	}
}
//*4遍歷
void Preorder(BiTree T,void(*visit)())// 先序遍歷二叉樹 
{                    

	if(T) 
	{
		(*visit)("%d\t",(T->data).key);                    // 訪問結點
	    Preorder(T->lchild, *visit);  // 遍歷左子樹
        Preorder(T->rchild, *visit); // 遍歷右子樹
    }
}
void Inorder(BiTree T,void(*visit)())// 中序遍歷二叉樹 
{                    
   if (T) 
   {
      Inorder(T->lchild,*visit);   // 遍歷左子樹
      (*visit)("%d  ",(T->data).key);                // 訪問結點
      Inorder(T->rchild,*visit);  // 遍歷右子樹
   } 
   
}

void main()
{
	BiTree T;
	int a[10]={503,87,512,061,908,170,897,275,653,426};
	TElemType b[10],e1,e2;
	int i;
	int key1,key2,key3;
	T=NULL;
	key1=653;
	key2=512;
	key3=87;
	e1.key=136;
	e2.key=56;
	for(i=0;i<=9;i++)	
		b[i].key=a[i];
	printf("想要建立的二叉排序樹中的節點為");
    for(i=0;i<=9;i++)
		printf("%d  ",b[i].key);
	printf("\n");
	printf("將這些節點插入到二叉排序數后，中序遍歷這個樹為\n");
	for(i=0;i<=9;i++)	InsertBST(&T,b[i]);
	Inorder(T,printf);
	printf("\n");
	printf("插入節點136后，中序遍歷這個樹為\n");
	InsertBST(&T,e1);
	Inorder(T,printf);
	printf("\n");
	printf("插入節點56后，中序遍歷這個樹為\n");
	InsertBST(&T,e2);
	Inorder(T,printf);
    printf("\ninsert over\n");
    printf("刪除節點653后，中序遍歷這個樹為\n");
	DeleteBST(T,NULL,key1);
	Inorder(T,printf);
	printf("\n");
	printf("刪除節點512后，中序遍歷這個樹為\n");
	DeleteBST(T,NULL,key2);
	Inorder(T,printf);
	printf("\n");
	printf("刪除節點87后，中序遍歷這個樹為\n");
	DeleteBST(T,NULL,key3);
	Inorder(T,printf);
	printf("\n");
}