#include"stdio.h"
#include"malloc.h"
#include"define.h"

typedef char TElemType;

typedef struct BiTNode	/*聲明二叉樹結點的形式*/
{
	TElemType data;		/*定義數據域*/
	struct BiTNode *lchild,*rchild,*parent;	/*定義左、右孩子及雙親指針*/
}BiTNode;

Status InitBiTree(BiTNode &T)
/*初始化二叉樹，即初始化頭結點*/
{
	if(&T==NULL)return ERROR;
	T.data=0;		/*頭結點數據域用以記錄二叉樹的節點*/
	T.parent=NULL;	/*將所有指針置零*/
	T.lchild=NULL;
	T.rchild=NULL;
	return OK;
}


Status CreatBiTree(BiTNode &T,BiTNode *Pparent,BiTNode *(&Pnow),int i)
/*遞歸添加二叉樹T結點，該結點由Pnow指向，其雙親結點由Pparent指向，
如果i=1,則添加為雙親結點的左結點，如果i=0,則添加為雙親結點的右結點*/
{
	
	char ch;	
	if(i==1)printf("\nEnter LEFT_CHILD for -%c- [<--] :",Pparent->data);
	else printf("\nEnter RIGHT_CHILD for -%c- [-->]:",Pparent->data);
	while((ch=getchar())==10);/*保證輸入的字符不為回車鍵*/
	if(ch==' ')Pnow=NULL;	/*如果輸入的字符為空白鍵，則不再為雙親結點添加該位置的孩子結點*/
	else	/*輸入字符為非空白鍵，添加孩子結點*/
	{
		if(!(Pnow=(BiTNode *)malloc(sizeof(BiTNode))))return ERROR;/*為新結點開辟內存單元*/
		Pnow->data=ch;	/*將字符值寫入數據域*/
		Pnow->parent=Pparent;	/*記錄雙親結點位置*/
		Pnow->lchild=NULL;
		Pnow->rchild=NULL;
		T.data++;	/*頭結點所記錄的結點數加1*/
		CreatBiTree(T,Pnow,Pnow->lchild,1);	/*為當前結點添加左孩子結點*/
		CreatBiTree(T,Pnow,Pnow->rchild,0);	/*為當前結點添加右孩子結點*/
	}
	return OK;/*添加結束，返回上級結點（雙親結點）*/
}

Status StrCreatBiTree(BiTNode &T,BiTNode *Pparent,BiTNode *(&Pnow),int i,char *str,int &j)
/*將字符串str的內容遞歸添加到二叉樹T結點，該結點由Pnow指向，其雙親結點由Pparent指向，
如果i=1,則添加為雙親結點的左結點，如果i=0,則添加為雙親結點的右結點*/
{
	
	char ch;	
	if((ch=str[j])=='^')Pnow=NULL;	/*如果字符串中的字符為^，則不再為雙親結點添加該位置的孩子結點*/
	else	/*輸入非^字符，添加孩子結點*/
	{
		if(!(Pnow=(BiTNode *)malloc(sizeof(BiTNode))))return ERROR;/*為新結點開辟內存單元*/
		Pnow->data=ch;	/*將字符值寫入數據域*/
		Pnow->parent=Pparent;	/*記錄雙親結點位置*/
		Pnow->lchild=NULL;
		Pnow->rchild=NULL;
		T.data++;	/*頭結點所記錄的結點數加1*/
		StrCreatBiTree(T,Pnow,Pnow->lchild,1,str,++j);	/*為當前結點添加左孩子結點*/
		StrCreatBiTree(T,Pnow,Pnow->rchild,0,str,++j);	/*為當前結點添加右孩子結點*/
	}
	return OK;/*添加結束，返回上級結點（雙親結點）*/
}

void printBiTree(BiTNode *Pnow)
/*遞歸輸出結點，輸出形式為：當前結點（左孩子結點，右孩子結點）*/
{
	printf("\n%c",Pnow->data);	/*輸出當前結點數據域*/
	if(Pnow->lchild!=NULL)printf("(%c,",Pnow->lchild->data);/*輸出左孩子結點數據域*/
	else printf("( ,");
	if(Pnow->rchild!=NULL)printf("%c)",Pnow->rchild->data);/*輸出右孩子結點數據域*/
	else printf(" )");
	if(Pnow->lchild!=NULL)printBiTree(Pnow->lchild);/*輸出左孩子結點*/
	if(Pnow->rchild!=NULL)printBiTree(Pnow->rchild);/*輸出右孩子結點*/
}

Status PrintElement(TElemType e)
/*輸出數據元素*/
{
	printf(" %c ",e);
	return OK;
}



Status PreOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*先序遍歷二叉樹，對數據元素用函數Visit訪問*/
{
	if(Pnow)/*檢驗當前結點是否為空*/
	{
		if(Visit(Pnow->data))/*調用Visit函數訪問當前數據元素*/
			if(PreOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不為空，遞歸調用PreOrderTraverse()*/
				if(PreOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不為空，遞歸調用PreOrderTraverse()*/
					return OK;/*調用結束，返回上一級函數*/
		return ERROR;
	}
	else return OK;
}

Status InOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*中序遍歷二叉樹，對數據元素用函數Visit訪問*/
{
	if(Pnow)
	{
		if(InOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不為空，遞歸調用InstOrderTraverse()*/
			if(Visit(Pnow->data))/*調用Visit函數訪問當前數據元素*/
				if(InOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不為空，遞歸調用InstOrderTraverse()*/
					return OK;
		return ERROR;	
	}
	else return OK;
}

Status PostOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*后序遍歷二叉樹，對數據元素用函數Visit訪問*/
{
	if(Pnow)
	{
		if(PostOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不為空，遞歸調用PoststOrderTraverse()*/
			if(PostOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不為空，遞歸調用PoststOrderTraverse()*/
				if(Visit(Pnow->data))/*調用Visit函數訪問當前數據元素*/
					return OK;
		return ERROR;	
	}
	else return OK;
}



void main()
{
	BiTNode T;
	Status (*Visit)(TElemType);
	char *str={"AB^^CDF^G^^^E^^"};
	char *str1={"ABC^^DE^G^^F^^^"};
	char *str2={"-+a^^*b^^-c^^d^^/e^^f^^"};
	int j=0;
	Visit=PrintElement;
	InitBiTree(T);	
	//CreatBiTree(T,&T,T.lchild,1);/*使用直接輸入方式建立二叉樹*/
	StrCreatBiTree(T,&T,T.lchild,1,str,j);/*使用字符串形式建立二叉樹*/	
	printf("\n T has %d node\n",T.data);
	printBiTree(T.lchild);
	printf("\nPreOrderTraverse: ");
	PreOrderTraverse(T.lchild,Visit);
	printf("\nInstOrderTraverse: ");
	InOrderTraverse(T.lchild,Visit);
	printf("\nPostOrderTraverse: ");
	PostOrderTraverse(T.lchild,Visit);
	N;
	
}