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

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

/*建立二叉树*/
PBiTree CreateBiTree();
/*先序遍历二叉树*/
void ProOrderTravel(PBiTree Tree);
/*中序遍历二叉树*/
void InOrderTravel(PBiTree Tree);
/*后序遍历二叉树*/
void PostOrderTravel(PBiTree Tree);

void main()
{
	PBiTree BTree = CreateBiTree();

	printf("先序排列为：\n");
	ProOrderTravel(BTree);
	printf("\n中序排列为：\n");
	InOrderTravel(BTree);
	printf("\n后序排列为：\n");
	PostOrderTravel(BTree);
	printf("\n");
}

PBiTree CreateBiTree()
{
	PBiTree T;
	ElemType tmp;
	scanf("%c",&tmp);

	if (tmp == '#')
	{
		T = NULL;
		return NULL;
	}
	else
	{
		T = (PBiTree)malloc(sizeof(BiTree));
		T->Elem = tmp;
		T->LChild = CreateBiTree();
		T->RChild = CreateBiTree();
	}

	return T;
}

void ProOrderTravel(PBiTree Tree)
{
	if (Tree != NULL)
	{
		printf("%c\t",Tree->Elem);
		ProOrderTravel(Tree->LChild);
		ProOrderTravel(Tree->RChild);
	}
}

void InOrderTravel(PBiTree Tree)
{
	if (Tree != NULL)
	{
		/* 如果有左子树，一直向下寻找 */
		if (Tree->LChild != NULL) 
		{
			InOrderTravel(Tree->LChild);
		}

		printf("%c\t",Tree->Elem);

		InOrderTravel(Tree->RChild);
	}
}

void PostOrderTravel(PBiTree Tree)
{
	if (Tree != NULL)
	{
		/* 如果有左子树，一直向下寻找 */
		if (Tree->LChild != NULL) 
		{
			PostOrderTravel(Tree->LChild);
		}

		PostOrderTravel(Tree->RChild);

		printf("%c\t",Tree->Elem);
	}
}