#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTree
{
    ElemType elem;
	BiTree * LChild;
	BiTree * RChild;
}BiTree,* PBiTree;

/*先序顺序创建二叉树*/
PBiTree CreateBiTree();
/*先序顺序遍历二叉树*/
void PreOrderTraverse(PBiTree T);
/*中序顺序遍历二叉树*/
void InOrderTraverse(PBiTree T);
/*后序顺序遍历二叉树*/
void PostOrderTraverse(PBiTree T);
/*遍历查找叶子节点*/
void TravelLeadNode(PBiTree T);
/*计算树的高度*/
int CountTreeHeight(PBiTree T);

int main()
{
	PBiTree Tree;
	int TreeHeight = 0;

	printf("按照先序顺序创建二叉树：\n");
	Tree = CreateBiTree();
	
	printf("\n按照先序顺序输出\n");	
	PreOrderTraverse(Tree);
	
	printf("\n按照中序顺序输出\n");	
	InOrderTraverse(Tree);
	
	printf("\n按照后序顺序输出\n");	
	PostOrderTraverse(Tree);
	
	printf("\n叶子结点为：\n");
	TravelLeadNode(Tree);

	TreeHeight = CountTreeHeight(Tree);
	printf("\n树的深度为：%d\n",TreeHeight);
	
	return 0;
}

PBiTree CreateBiTree()
{
	PBiTree Tree = NULL;
	ElemType elem = '\0';
	scanf("%c",&elem);
	
	if (elem == '#')
	{
		Tree = NULL;
	}
	else
	{
		Tree = (PBiTree)malloc(sizeof(BiTree));
		Tree->elem = elem;
		Tree->LChild = CreateBiTree();
		Tree->RChild = CreateBiTree();
	}
	
	return Tree;
}


void PreOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		printf("%c ",T->elem);
		
		PreOrderTraverse(T->LChild);
		PreOrderTraverse(T->RChild);
	}
	else 
		return;
}


void InOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild != NULL)
		{
			InOrderTraverse(T->LChild);
		}
		
		printf("%c ",T->elem);	
		InOrderTraverse(T->RChild);	
	}
}


void PostOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild != NULL)
		{
			PostOrderTraverse(T->LChild);
		}
		
		PostOrderTraverse(T->RChild);	
		printf("%c ",T->elem);
	}
}


void TravelLeadNode(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild == NULL && T->RChild == NULL)
		{
			printf("%c ",T->elem);
		}
		
		TravelLeadNode(T->LChild);
		TravelLeadNode(T->RChild);
	}
}


int CountTreeHeight(PBiTree T)
{
	if (T != NULL)
	{
		return	CountTreeHeight(T->LChild) > CountTreeHeight(T->RChild) 
			? CountTreeHeight(T->LChild)+1 : CountTreeHeight(T->RChild)+1;
	}
	else
	{
		return 0;
	}
}