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