poj2255解题报告～

1.算法
本题是给出一个树的先序和中序，输出它的后序。可以通过递归实现。
举例说明
先序：DBACEGF 中序：ABCDEFG
（1）把整个7个字符作为一段，根据先序找出第一个根D，根据中序可以得出，D左边为ABC，右边为EFG。
（2）对D两边递归进行（1）操作。
（3）递归的终止条件是这一段中只有一个字符（即为叶结点）
根据以上可以步骤可以生成一棵树，然后递归输出后序。
ps：
后来发现可以不用生成树的结构，直接递归完成，即在生成树的递归函数中进行后序输出。
2.实现
（1）对于没有给定行的输入可以用 while(cin>>str1>>str2)进行判断，对于如何用scanf函数判断有待解决
（2）不知道为什么我的程序在c++环境中可以成功运行，而在g++环境中发生Output Limit Exceeded的错误，有待解决
3.代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

char str1[26],str2[26];

void func(int p,int q,int len);
int main()
{
int len=0;
while(cin>>str1>>str2)
{
len=strlen(str1);
func(0,0,len);
printf("\n");
}
return 0;
}
void func(int p,int q,int len)
{
if(len==1)
{
printf("%c",str1[p]);
return;
}
int x=q;
while(str2[x]!=str1[p])x++;
int len1=x-q;
int len2=len-(1+x-q);

if(len1>0)func(p+1,q,len1);
if(len2>0)func(p+1+len1,x+1,len2);
printf("%c",str2[x]);
}