题意：
给出先序和中序，求后序。
思路：
①建树然后递归输出。
//建树的
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std; int n;
char pre[],mid[];
int judge[];
struct node{ char c;
node *left,*right;
node()
{
c='a';
left=right=NULL;
}
};
int cnt=,counter;
node* build(node *root)
{
char c=pre[cnt++];//从a中取数 去b中查找
int i;
for( i=;i<n;i++)
{
if(mid[i]==c)
break;
}
judge[i]=;
root=new node();
root->c=c;
if(i>&&i<n&&judge[i-]!=)//在b数组中，如果一个数左相邻的数被标记，则不能向左建树
root->left=build(root->left);
if(i>=&&i<n-&&judge[i+]!=)//同样，在b数组中，如果一个数右相邻的数被标记，则不能向右建树
root->right=build(root->right);
return root; //左右都建完，返回根结点
} void postorder(node *root)
{
if(root->left)
postorder(root->left);
if(root->right)
postorder(root->right);
if(counter)
//printf(" ");
//counter++;
printf("%c",root->c);
} int main()
{
while(scanf("%s %s",pre,mid)==)
{
//printf("%s %s\n",pre,mid);
counter = ;
cnt = ;
n=strlen(pre);
memset(judge,,sizeof(judge)); node *root = NULL;
root = build(root);
postorder(root);
printf("\n");
}
return ;
}
②不建树直接输出。
//不建树
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std; int n;
char pre[],mid[];
int cnt=,counter;
void work(int left,int right)//左右端点
{
int i;
char c=pre[cnt++];
for(i=left;i<right;i++)
{
if(mid[i]==c)
break;
}
if(i>left&&i<right)
work(left,i);
if(i>=left&&i<right-)
work(i+,right);
printf("%c",c);
} int main()
{
while(scanf("%s %s",pre,mid)==)
{
//printf("%s %s\n",pre,mid);
counter = ;
cnt = ;
n=strlen(pre); work(,n);
printf("\n");
}
return ;
}