C语言 先序序列创建二叉树【树和二叉树】给定先序序列，按照该序列创建对应的二叉树，输出其中序和后序序列。输入：一行二叉树按先序遍历序列，空指针用字符^占位，输出：两行，分别对应该二叉树的中序和后序序列

Description

给定先序序列，按照该序列创建对应的二叉树，并输出其中序和后序序列。

Input

一行，二叉树按先序遍历序列，空指针用字符^占位

Output

两行，分别对应该二叉树的中序和后序序列

Sample Input
ABC^^DEG^^F^^

Sample Output
CBEGDFA
CGEFDBA

#include<malloc.h>
#include<stdio.h>
#define  TElemType char 
//二叉树的二叉链表的表示与实现 
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序遍历 
void PreOrderTarverse(BiTree T,void (*visit)(TElemType))
{
	if(T)
	{
		visit(T->data)	;
		PreOrderTarverse(T->lchild,visit);
		PreOrderTarverse(T->rchild,visit);
	}
} 
//中序遍历 
void InOrderTarverse(BiTree T,void (*visit)(TElemType))
{
	if(T)
	{		
		InOrderTarverse(T->lchild,visit);
		visit(T->data);
		InOrderTarverse(T->rchild,visit);
	}
}
//后序遍历 
void PostOrderTarverse(BiTree T,void (*visit)(TElemType))
{
	if(T)
	{		
		PostOrderTarverse(T->lchild,visit);
		PostOrderTarverse(T->rchild,visit);
		visit(T->data);
	}
}

//先序创建二叉树 ，假设树中结点为字符型，以^代表为空结点 
BiTree CreateBiTree()
{
	char ch;
	BiTree T;
	ch=getchar();
	if(ch=='^')
		T=NULL;
	else
	{
		T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data=ch;
		T->lchild =CreateBiTree();
		T->rchild =CreateBiTree();
	}
	return T;
}
void visit(char e)
{
	printf("%c",e);
 } 


int main()
{
	BiTree T;
	T=CreateBiTree();
	//中序序列 
	InOrderTarverse(T,visit);
	//每个序列输出之后换行 
	printf("\n");
	//后序序列 
	PostOrderTarverse(T,visit);
	return 0; 
 }