#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=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;
}