#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>  
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存盤空間初始分配量 */

typedef int Status;		/* Status是函式回傳的型別*/

/* 用于構造二叉樹 */
int treeIndex = 1;
typedef char String[MAXSIZE]; /*  0號單元存放串的長度 */
String str; // str為初始化的字串 
FILE *fp;   // 保存用的檔案指標 

typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符為空 */

typedef struct BiTNode  /* 結點結構 */
{
   TElemType data;		/* 結點資料 */
   struct BiTNode *lchild,*rchild; /* 左右孩子指標 */
}BiTNode,*BiTree;

/* 非遞回使用的堆疊 */
typedef struct Stack
{
	BiTree s[MAXSIZE];
	int top;	
}Stack;

/* 層序遍歷使用的佇列 */
typedef struct Queue
{
	BiTree q[MAXSIZE];
	int head;
	int tail;
}Queue;

Status StrAssign(String T,char *chars);	// 前序遍歷初始化 
Status visit(TElemType e);				// 訪問樹的節點元素	
Status InitBiTree(BiTree *T);			// 初始化 
void DestroyBiTree(BiTree *T);			// 釋放二叉樹 
void CreateBiTree(BiTree *T);			// 建立二叉樹
Status BiTreeEmpty(BiTree T);			// 判空 
int BiTreeDepth(BiTree T);				// 求二叉樹的深度 
TElemType Root(BiTree T);				// 求二叉樹的根節點 
TElemType Value(BiTree p);				// 回傳該節點的值 
void Assign(BiTree p,TElemType value);	// 給二叉樹的節點賦值 
void PreOrderTraverseRec(BiTree T);		// 前序遍歷遞回版 
void PreOrderTraverse(BiTree T);		// 前序遍歷非遞回版 
void InOrderTraverseRec(BiTree T);		// 中序遍歷遞回版 
void InOrderTraverse(BiTree T);			// 中序遍歷非遞回版 
void PostOrderTraverseRec(BiTree T);	// 后序遍歷遞回版 
void PostOrderTraverse(BiTree T);		// 后序遍歷非遞回版 
void SeqTraverse(BiTree T);				// 層序遍歷 
int CalcuWidth(BiTree T);				// 回傳二叉樹的最大寬度 
Status JudgeCBT(BiTree T);				// 判斷是否為完全二叉樹 


int main(int args, char * argv[])
{
	BiTree T;
	InitBiTree(&T);
	
	FILE *infile = fopen("in.txt","r");
	
	fp = fopen("out.txt","w");
	if(fp == NULL || infile == NULL)
	{
		(void) fprintf (stderr, "File open error!\n");//錯誤輸出流 
		exit(EXIT_FAILURE);
	}
	
	String input;
	fprintf(stdout,"please input BinaryTree with Preorder:(Empty Node with #)\n");
	fscanf(infile,"%s", input);
	StrAssign(str,input);
	
	fprintf(stdout,"%s\n",input);
	fprintf(fp,"%s\n",input);
	
	CreateBiTree(&T);
	
	fprintf(stdout,"\nPreOrderTraverseRec:");
	fprintf(fp,"\nPreOrderTraverseRec:");
	PreOrderTraverseRec(T);
	
	fprintf(stdout,"\nPreOrderTraverse:");
	fprintf(fp,"\nPreOrderTraverse:");
	PreOrderTraverse(T);
	
	fprintf(stdout,"\nInOrderTraverseRec:");
	fprintf(fp,"\nInOrderTraverseRec:");
	InOrderTraverseRec(T);
	
	fprintf(stdout,"\nInOrderTraverse:");
	fprintf(fp,"\nInOrderTraverse:");
	InOrderTraverse(T);
	
	fprintf(stdout,"\nPostOrderTraverseRec:");
	fprintf(fp,"\nPostOrderTraverseRec:");
	PostOrderTraverseRec(T);
	
	fprintf(stdout,"\nPostOrderTraverse:");
	fprintf(fp,"\nPostOrderTraverse:");
	PostOrderTraverse(T);
	
	fprintf(stdout,"\nSeqTraverse:");
	fprintf(fp,"\nSeqTraverse:");
	SeqTraverse(T);
	
	fprintf(stdout,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T)); 
	fprintf(fp,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T)); 
	
	fprintf(stdout,"BiTree`s width:%d\n",CalcuWidth(T));
	fprintf(fp,"BiTree`s width:%d\n",CalcuWidth(T));

	DestroyBiTree(&T);
	
	fclose(fp);
	fclose(infile);
	
	return 0;
}



Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars) > MAXSIZE)
		return ERROR;
	else
	{
		T[0] = strlen(chars);
		for(i = 1;i <= T[0]; i ++ )
			T[i] = *(chars + i - 1);
		return OK;
	}
}

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 構造空二叉樹T */
Status InitBiTree(BiTree *T)
{ 
	*T=NULL;
	return OK;
}

/* 初始條件: 二叉樹T存在，操作結果: 銷毀二叉樹T */
void DestroyBiTree(BiTree *T)
{ 
	if(*T) /* 遞回的銷毀，類似于后序遍歷 */ 
	{
		if((*T)->lchild) /* 有左孩子 */
			DestroyBiTree(&(*T)->lchild); /* 銷毀左孩子子樹 */
		if((*T)->rchild) /* 有右孩子 */
			DestroyBiTree(&(*T)->rchild); /* 銷毀右孩子子樹 */
		free(*T); /* 釋放根結點 */
		*T = NULL; /* 空指標賦NULL */
	}
}

/* 按前序輸入二叉樹中結點的值（一個字符） */
/* #表示空樹，構造二叉鏈表表示二叉樹T， */
void CreateBiTree(BiTree *T)
{ 
	TElemType ch;
	
	/* scanf("%c",&ch); */
	ch=str[treeIndex ++];

	if(ch == '#') 
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if(!*T)
		{
			(void) fprintf (stderr, "Cannot allocate memory!\n");//錯誤輸出流 
			exit(OVERFLOW);
		} 
			
		(*T)->data=https://www.cnblogs.com/Az1r/archive/2022/10/15/ch; /* 生成根結點 */
		CreateBiTree(&(*T)->lchild); /* 構造左子樹 */
		CreateBiTree(&(*T)->rchild); /* 構造右子樹 */
	}
}

/* 初始條件: 二叉樹T存在 */
/* 操作結果: 若T為空二叉樹,則回傳TRUE,否則FALSE */
Status BiTreeEmpty(BiTree T)
{ 
	if(T)
		return FALSE;
	else
		return TRUE;
}


/* 初始條件: 二叉樹T存在，操作結果: 回傳T的深度 */
int BiTreeDepth(BiTree T)
{
	int i, j;
	if(!T)
		return 0;
	if(T->lchild)
		i = BiTreeDepth(T->lchild);
	else
		i = 0;
	if(T->rchild)
		j = BiTreeDepth(T->rchild);
	else
		j = 0;
	return i > j ? i+1 : j+1;
}

/* 初始條件: 二叉樹T存在，操作結果: 回傳T的根 */
TElemType Root(BiTree T)
{ 
	if(BiTreeEmpty(T))
		return Nil;
	else
		return T->data;
}

/* 初始條件: 二叉樹T存在，p指向T中某個結點 */
/* 操作結果: 回傳p所指結點的值 */
TElemType Value(BiTree p)
{
	return p->data;
}

/* 給p所指結點賦值為value */
void Assign(BiTree p,TElemType value)
{
	p->data=value;
}

/* 前序遞回遍歷 */
void PreOrderTraverseRec(BiTree T)
{ 
	if(T == NULL)
		return;
	fprintf(stdout,"%c",T->data);/* 顯示結點資料，可以更改為其它對結點操作 */
	fprintf(fp,"%c",T->data);
	PreOrderTraverseRec(T->lchild); /* 再先序遍歷左子樹 */
	PreOrderTraverseRec(T->rchild); /* 最后先序遍歷右子樹 */
}

/* 前序非遞回遍歷 */
void PreOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;
	
	while(T || stk.top)
	{
		if(T)
		{
			fprintf(stdout,"%c",T->data);// 先列印根節點 
			fprintf(fp,"%c",T->data);
			stk.s[++ stk.top] = T;// 入堆疊 
			T = T->lchild;//  遞回左節點 
		}else
		{
			T = stk.s[stk.top --]; // 回溯 
			T = T->rchild; 		   // 遞回右節點 
		}
	}
}

/* 中序遞回遍歷 */
void InOrderTraverseRec(BiTree T)
{ 
	if(T == NULL)
		return;
	InOrderTraverseRec(T->lchild); /* 中序遍歷左子樹 */
	fprintf(stdout,"%c",T->data);/* 顯示結點資料，可以更改為其它對結點操作 */
	fprintf(fp,"%c",T->data);
	InOrderTraverseRec(T->rchild); /* 最后中序遍歷右子樹 */
}
/* 中序非遞回遍歷 */
void InOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;
	
	while(T || stk.top)
	{
		if(T)
		{
			stk.s[++ stk.top] = T; /* 入堆疊，遞回左節點  */ 
			T = T->lchild;
		}else
		{
			T = stk.s[stk.top --]; /* 出堆疊，回溯，列印根節點 */ 
			fprintf(stdout,"%c",T->data);
			fprintf(fp,"%c",T->data);
			T = T->rchild;		   /* 遞回右節點 */ 
		}
	}
}

/* 后序遞回遍歷 */
void PostOrderTraverseRec(BiTree T)
{
	if(T == NULL)
		return;
	PostOrderTraverseRec(T->lchild); /* 先后序遍歷左子樹  */
	PostOrderTraverseRec(T->rchild); /* 再后序遍歷右子樹  */
	fprintf(stdout,"%c",T->data);/* 顯示結點資料，可以更改為其它對結點操作 */
	fprintf(fp,"%c",T->data);
}

/* 后序非遞回遍歷 */
void PostOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;

	BiTree right = NULL; /*上一次遍歷到的右節點 */ 
	while(T || stk.top)
	{
		if(T)
		{
			stk.s[++ stk.top] = T; /* 不斷向左遞回 */ 
			T = T->lchild;
		}else
		{
			T = stk.s[stk.top];
			
			if(T->rchild && T->rchild != right) /* 向右 */ 
			{
				T = T->rchild;
			}else /* 左右都不行的話，回溯，列印當前結點 */ 
			{
				stk.top --;
				fprintf(stdout,"%c",T->data);
				fprintf(fp,"%c",T->data);
				right = T;
				T = NULL;/* 防止死回圈 */ 
			}
		}
	}
}

/* 層序遍歷 */ 
void SeqTraverse(BiTree T)
{
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	
	while(qu.head <= qu.tail) /* 列印隊頭的元素，再將隊頭的元素的左右兒子入隊 */ 
	{
		int lenth = qu.tail - qu.head + 1;
		while(lenth --)
		{
			BiTree root = qu.q[qu.head ++];
			fprintf(stdout,"%c",root->data);
			fprintf(fp,"%c",root->data);
			if (root->lchild)
				qu.q[++ qu.tail] = root->lchild;
			if(root->rchild)
				qu.q[++ qu.tail] = root->rchild;
		}
	}
}

/* 寬度計算 */ 
int CalcuWidth(BiTree T)
{
	if(T == NULL) return 0;
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	int res = 0; 
	
	while(qu.head <= qu.tail) 
	{
		int lenth = qu.tail - qu.head + 1;//一行一行的取寬度最大值
		if(res < lenth) res = lenth;
		while(lenth --)
		{
			BiTree root = qu.q[qu.head ++];
			if (root->lchild)
				qu.q[++ qu.tail] = root->lchild;
			if(root->rchild)
				qu.q[++ qu.tail] = root->rchild;
		}
	}
	return res;
}
/* 判斷是否為完全二叉樹 */ 
Status JudgeCBT(BiTree T)
{
	if(T == NULL)
	{
		return TRUE;
	}
	
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	
	while(qu.head <= qu.tail) /* 列印隊頭的元素，再將隊頭的元素的左右兒子入隊 */ 
	{
		BiTree root = qu.q[qu.head ++];
		
		if(root == NULL)
		{
			break;
		}

		qu.q[++ qu.tail] = root->lchild;
			
		qu.q[++ qu.tail] = root->rchild;
	}
	
	while(qu.head <= qu.tail)
	{
		if(qu.q[qu.head ++] != NULL)
		{
			return FALSE;
		}
	}
	return TRUE;
}