#include"stdio.h"
#include"malloc.h"
#define size  100
#define  SIZE 10
#define  MORE 10 
#define OK 1
#define ERRO 0
int n;   /*統(tǒng)計(jì)插入的結(jié)點(diǎn)個(gè)數(shù)*/

/*二叉樹結(jié)構(gòu)體定義*/
typedef struct BST{
int data;
BST *lchild;
BST *rchild;
}BST;

/*隊(duì)列的結(jié)構(gòu)類型定義*/
typedef struct{
BST *base;
int front;
int rear;
}SqQueue;

/*棧的結(jié)構(gòu)類型定義*/
typedef struct{
BST *base;
BST *top;
int stacksize;
}SqStack;

SqQueue Q;/*隊(duì)列變量 Q*/


/************ 主菜單************/
void menu(){
printf("\n1、insert:");
printf("\n2、diaplay:");
printf("\n3、search:");
printf("\n4、Inorder(非遞歸):");
printf("\n5、depth:");
printf("\n6、joint:");
printf("\n7、Layer:");
printf("\n8、Change:");
printf("\n0、quit:");
printf("\nchoose: "); 
}



/************ 構(gòu)建空二叉樹************/
BST *InitBST(){
BST *T;
T=(BST *)malloc(sizeof(BST));
if(!T)return NULL;
T->lchild=NULL;
T->rchild=NULL;
n=0;
return T;
}

/****空樹的判斷************/
int EmptyBST(int n){
	if(n==0){
		printf("The tree is empty,unanble to display!!\n");
		return OK;
	}
else return ERRO;
}

/********查找函數(shù)********/
int search(BST *T,int e){
	if(T){  
		/*判斷查找的結(jié)點(diǎn)是否存在*/
		/*要查找的結(jié)點(diǎn)大于比較的結(jié)點(diǎn),即向右子樹查找*/
		/*要查找的結(jié)點(diǎn)小于比較的結(jié)點(diǎn),即向左子樹查找*/
		if((T->data==e)?1:((e>T->data)?search(T->rchild,e):search(T->lchild,e)))
			return OK;
	else return ERRO;
	}
    else return 0;

}
/************ 插入操作************/
BST *InsertBST(BST *T){
BST *p,*q;
int GO=1;
int x;
p=T;
printf("please intput the joint: ");
scanf("%d",&x);
if(n==0){
T->data=x;
printf("The joint inserts successful!\n");
}
else{
	/*調(diào)用查找函數(shù)判斷待插入的結(jié)點(diǎn)是否已存在*/
	/*已存在即不再插入該元素*/
	/*不存在即插入該結(jié)點(diǎn)*/
	if(!search(T,x)){
q=(BST *)malloc(sizeof(BST));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
while(GO){
if(x>p->data)
p->rchild==NULL?(GO=0,p->rchild=q):p=p->rchild;
else
p->lchild==NULL?(GO=0,p->lchild=q):p=p->lchild;
	}
printf("The joint has been inserted!\n");
	}
	else {
		printf("The number have been inserted!\n");
    	printf("So there couldnot insert again!");
	}
}
n++;
return T;
}

/*棧的各類操作*/
/*********初始化棧*******/
void Initstack(SqStack &L){
	L.stacksize=SIZE;
	L.base=(BST *)malloc(L.stacksize*sizeof(BST));
	L.top=L.base;
}

/************push()進(jìn)棧***********/
void push(SqStack &L,BST *e)
{  
	if(L.top-L.base>=L.stacksize)
	{
		L.base=(BST *)realloc(L.base,(L.stacksize+MORE)*sizeof(BST));
		if (!L.base)  printf("error!\n");
		L.top=L.base+L.stacksize;
		L.stacksize+=MORE;
	}
	L.top->data=e->data;
		L.top->lchild=e->lchild;
			L.top->rchild=e->rchild;
L.top++;
}
/*************pop()出棧***************/
BST *Pop(SqStack &L){

	if(L.base==L.top)
		return NULL;
	else
	   return(--L.top);
}
/**********空棧判斷**********/
int StackEmpty(SqStack L){
if(L.base==L.top)return OK;
else return ERRO;
}

/*隊(duì)列的各項(xiàng)操作*/
/********隊(duì)列初始化*******/
void Init(SqQueue &Q){   
Q.base=(BST *)malloc(size*sizeof(BST));
if(!Q.base)printf("\n空間分配失敗!\n");
else{Q.front=Q.rear=0;}
}
/******隊(duì)空判斷*******/
int EmptyQueue(SqQueue Q){   
if(Q.rear==Q.front)  
	return 1;
else return 0;
}
/*****入隊(duì)處理*******/
void EnQueue(SqQueue &Q,BST*e){    
Q.base[Q.rear].data=e->data;
Q.base[Q.rear].lchild=e->lchild;
Q.base[Q.rear].rchild=e->rchild;
Q.rear=(Q.rear+1)%size;
}
/******出隊(duì)處理******/
void DeQueue(SqQueue &Q){  
if(EmptyQueue(Q));
else 
	Q.front=(Q.front+1)%size;
}
/******讀取隊(duì)頭元素*******/
BST* TopQueue(SqQueue Q){  
	if(EmptyQueue(Q))return NULL;
else
return&(Q.base[Q.front]);
}

/************ 前序遍歷遞歸************/
void PreOrderTraverse(BST *T){
if(T)printf("%d  ",T->data);
if(T->lchild)PreOrderTraverse(T->lchild);
if(T->rchild)PreOrderTraverse(T->rchild);
}
/************ 中序遍歷非遞歸************/
void InorderTraverse(BST *T){
	SqStack L;
	BST *p;
	p=T;
    Initstack(L);
	if(EmptyBST(n))return;
	while(p||!StackEmpty(L)){
		if(p){push(L,p);p=p->lchild;}
		else{
		p=Pop(L);
		if(p)printf("%d  ",p->data);
		p=p->rchild;
		}
	}
}
/************ 中序遍歷遞歸************/
void InOrderTraverse(BST *T){
if(T->lchild)InOrderTraverse(T->lchild);
if(T)printf("%d  ",T->data);
if(T->rchild)InOrderTraverse(T->rchild);
}
/************ 后序遍歷遞歸************/
void PostOrderTraverse(BST *T){
	if(T->lchild){
	
    PostOrderTraverse(T->lchild);
	}
	if(T->rchild){
   PostOrderTraverse(T->rchild);
	
	}printf("%d  ",T->data);
}
/**************深度depth()**************/
int Depth(BST *T)             
{int n=-1;
int l,r;
if(T)
{r=Depth(T->rchild);
l=Depth(T->lchild);
if(r>=l)
n=r;
if(l>=r)
n=l;}	
return (n+1);}
/***************結(jié)點(diǎn)數(shù)*****************/
void joint(BST*T,int &N){
if(T->lchild==NULL&&T->rchild==NULL)
N+=1;
if(T->lchild)joint(T->lchild,N);
if(T->rchild)joint(T->rchild,N);
}
/***********Change交換結(jié)點(diǎn)***********/
void Change(BST *T){
BST *p;
if(T->lchild)
Change(T->lchild);
if(T->rchild)
Change(T->rchild);
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
}

/************層次輸出*************/
void Layer(BST *T){
if(T->lchild)EnQueue(Q,T->lchild);
if(T->rchild)EnQueue(Q,T->rchild);
printf("%d  ",*TopQueue(Q));
DeQueue(Q);
if(EmptyQueue(Q))return;
Layer(TopQueue(Q));
}


/************輸出相關(guān)處理函數(shù)************/
void output(BST*T){
if(EmptyBST(n))return;
printf("\npreOrderTraverse::  ");
PreOrderTraverse(T);
printf("\nInOrderTraverse::   ");
InOrderTraverse(T);
printf("\npostTraverse:: ");
PostOrderTraverse(T);
}
/************ 主函數(shù)************/
void main(){
BST *T;
int e,N;
int sel=3;
T=InitBST();
while(sel){
menu();
scanf("%d",&sel);
switch(sel){
case 1:
	T=InsertBST(T);
	break;
case 2:
	output(T);
	break;
case 3:
	printf("\nplease input a joint: ");
	scanf("%d",&e);
	if(search(T,e))
		printf("\nFind it!\n");
	else printf("\nUnfound!\n");
	break;
case 4:	
	if(T)printf("InOrderTraverse: ");
	InorderTraverse(T);
	break;
case 5:
	printf("The depth of the tree: ");
	if(n==0)printf("0");
	else
	printf(" %d",Depth(T));
	break;
case 6:
	N=0;
    joint(T,N);
	printf("There is %d joints!",N);
	break;
case 7:
	if(EmptyBST(n))break;
	Init(Q);
	printf("Data output by layer: ");
	EnQueue(Q,T);
	Layer(T);break;
case 8:Change(T);
	printf("The chilren of the joint have been changed!");
	break;
} 
}
}