树--遍历

树的遍历

已知二叉树的一个按先序遍历输入的字符序列，如abc,de,g,f, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

Input
连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。

Output
每组输入数据对应输出2行：
第1行输出中序遍历序列；
第2行输出后序遍历序列。

Sample Input
abc,de,g,f,

Sample Output
cbegdfa
cgefdba

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;

//定义树的节点 ,每个节点都有数据，左右孩子 
typedef struct tree     
{
	char data;            //数据元素
	struct tree *l,*r;    //左孩子节点，右孩子节点 
}tree;                 //二叉链中节点类型

int i;
char s[55];

//开辟新节点，申请新节点的空间，并且左右孩子为空 
tree *newtree()   
{
	tree *t;
	t = (tree *)malloc(sizeof(tree));
	t->r = t->l = NULL;
	return t; 
} 

//根据给出的字符串建树 
tree *creat()   
{
	tree *t = newtree();    //建立新节点 他
	if(s[i++] == ',')
		return NULL;
	
	t->data = s[i-1];
	t->l = creat();
	t->r = creat();
	return t;
	
}


//中序遍历
void show_mid(tree *t) 
{
	if(t)
	{
		show_mid(t->l);
		cout << t->data ;
		show_mid(t->r);
	}
 } 
 
 //后序遍历
 
void show_back(tree *t)
{
	
	if(t)
	{
		show_back(t->l);
		show_back(t->r);
		cout << t->data;
	}
 } 
 
 
int main()
{
	tree *t;
	
	while(scanf("%s",s)!=EOF)
	{
		i = 0;
		t = newtree();
		t = creat();
		show_mid(t);
		cout << endl;
		show_back(t);
		cout << endl;
	}	
	
	return 0;
}