ZOJ - 1944(Tree Recovery)(二叉树重建)(前序遍历,中序遍历推导后序遍历)
题目:
题目链接:ZOJ Problem Set - 1944
类似问题可以看看我的另一篇博文:前序遍历,中序遍历推导后序遍历
题目大意:
输入两个字符串表示一个二叉树的前序遍历和中序遍历
要求输出该二叉树的后序遍历
思路:
通过前序遍历和后序遍历把二叉树重新建立,再对二叉树进行后序遍历打印
代码:
#include <cstdio>
#include<cstring>
#include<stdlib.h>
using namespace std;
char a[30],b[30];
struct tree//一个结构体表示一个节点
{
tree *ltree;//左子树
tree *rtree;//右子树
char date;//值
};
tree* builder(char *a,char *b,int s)
{
tree *t;
for(int i=0; i<s; i++)
{
if(a[0]==b[i])
{
t=(tree*)malloc(sizeof(tree));
t->date=a[0];
t->ltree=builder(a+1,b,i);
t->rtree=builder(a+i+1,b+i+1,s-i-1);
return t;
}
}
return NULL;
}
void put(tree *t)//对建立的二叉树进行后序遍历
{
if(t)
{
put(t->ltree);
put(t->rtree);
printf("%c",t->date);
}
}
int main()
{
while(~scanf("%s",a))
{
tree *root;
scanf("%s",b);
int s=strlen(a);
root=builder(a,b,s);
put(root);
putchar('\n');
}
return 0;
}