#include <malloc.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h> //exit()

#define OK 1
#define NULL 0
#define FALSE 0

typedef struct BiTNode{ //定義鏈式二叉樹結構體
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;
char ch;
int flag=0;

int createBiTree(BiTree &T){
	//按先序輸入二叉樹中結點的值（一個字符），空格表示空樹
	ch=getchar();
	if(ch==' ')T=NULL; //表示空樹
	else if(ch==10)flag=1;  //結點信息輸入錯誤則返回0
	else {
		T=(BiTNode*)malloc(sizeof(BiTree));
		if(!T)exit(1);//空間分配不成功則退出
		T->data=ch;                //生成根結點
		createBiTree(T->lchild);   //生成左子樹
		createBiTree(T->rchild);   //生成右子樹
	}//else
	return OK;
}//createBiTree

int PreOrderTraverse(BiTree T){   //先序遍歷二叉樹的遞歸算法
	if(T){
		printf("%c",T->data);        //訪問根結點
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}//if
	return OK;
}

int InOrderTraverse(BiTree T){   //中序
	if(T){
		InOrderTraverse(T->lchild);
		printf("%c",T->data);        //訪問根結點
		InOrderTraverse(T->rchild);
	}//if
	return OK;
}

int PostOrderTraverse(BiTree T){ // 后序
	if(T){
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%c",T->data);        //訪問根結點
	}
	return OK;
}

int NodeCount(BiTree T){ //
    if(T==NULL) return 0;// 如果是空樹，則結點個數為0
    else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
//否則結點個數為1+左子樹的結點個數+右子樹的結點個數
}

int LeafNodeCount(BiTree T ){
	if(!T)return 0; //如果是空樹，則葉子個數為0; 
	else if(LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild)==0)return 1;//如果是葉子結點，則葉子結點個數為1
	else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
        //否則葉結點個數為左子樹的葉結點個數+右子樹的葉結點個數
} 


int  Depth(BiTree T){//計算二叉樹的深度
	int m,n;
	if(T==NULL )return 0;//如果是空樹，則深度為0
	else {
		m=Depth(T->lchild);//計算左子樹的深度記為m
		n=Depth(T->rchild);//計算右左子樹的深度記為n
		if(m>n) return(m+1);//二叉樹的深度為m 與n的較大者加1
		else  return (n+1);
	}
}

void main(){
	int no,out=1;
	char choose;
//*****************************主界面**********************************
	while(out){
		system("cls");
		printf("\n這是實驗3的程序，請按照說明使用：\n");
		printf("1．以二叉鏈表表示二叉樹，建立一棵二叉樹，請輸入1");
		printf("\n2．輸出二叉樹的前序遍歷結果，請輸入2");
		printf("\n3．輸出二叉樹的中序遍歷結果，請輸入3");
		printf("\n4．輸出二叉樹的后序遍歷結果請輸入4");
		printf("\n5．統計二叉樹的結點個數，請輸入5");
		printf("\n6．統計二叉樹的葉結點個數，請輸入6");
		printf("\n7．計算二叉樹的深度，請輸入7");
		printf("\n8．退出，請輸入其他\n");
//********************處理輸入的選項************************************
	choose=getch();
	switch(choose){
		case '1':
			system("cls");
			printf("\n請輸入二叉鏈表各結點信息建立二叉樹，空樹用空格表示：\n");
			if(createBiTree(T)==0||flag==1){   //結點輸入錯誤！
				printf("輸入錯誤，請重新輸入結點信息!\n"); 
				getch();break;}
			else
			printf("輸入完畢！");//成功建立二叉鏈表
			getch();break;
		case '2':
			printf("\n先序遍歷的結果是：");
			PreOrderTraverse(T);
			getch();break;
		case '3':
			printf("\n中序遍歷的結果是：");
			InOrderTraverse(T);
			getch();break;
		case '4':
			printf("\n后序遍歷的結果是：");
			PostOrderTraverse(T);
			getch();break;
		case '5':
			no=NodeCount(T);
			printf("\n總結點個數為:%d\n",no);
			getch();break;
		case '6': 
			printf("\n葉子結點的個數為:%d\n",LeafNodeCount(T));
			getch();break;
		case '7': 
			printf("\n二叉樹深度為：%d\n",Depth(T));
			getch();break;
		default :
			printf("\n你輸入的是:其他\n");
			getch();
			out=0;
		} //end switch
	}//end of while
	system("cls");
	printf("\n\n\t\t歡迎使用，再見！");
}