扩展后序遍历构建一棵二叉树

时间限制 : 1.000 sec 内存限制 : 128 MB

【 题目描述 】

给定一棵二叉树的扩展后序序列，试构造这个二叉树，并输出这个二叉树的前序遍历结果。

【 输入 】

一行字符，即扩展后序序列，字符只包含大写字母和“.”，长度不超过255

【 输出 】

输出对应的前序遍历结果

【 样例输入 】

..a..b.cd

【 样例输出 】

dacb

#include <iostream>
#include <cstring>
using namespace std;
struct node{
	char value;
	int l,r;
}data[102];
char c[102];
int s=0;
int root,cnt=0;
int Btree(int bt)
{
	cin>>c;
	if(c=='.'){
		bt=0;
	}else{
		bt=++s;
		data[bt].value=c;
		data[bt].l=data[bt].r=0;
		data[bt].l=Btree(bt);
		data[bt].r=Btree(bt);
	}
	return bt;
}
void ldr(int bt)
{
	if(bt)
	{
		ldr(data[bt].l);
		cout<<data[bt].value;
		ldr(data[bt].r);
	}
}
int main()
{
	cin>>c;
	cnt=strlen(c)-1;
	root=Btree(0);
	ldr(root);
	return 0;
}