2001年NOIP全国联赛普及组
题目描述 Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入描述 Input Description
两个字符串，分别是中序和后序（每行一个）
输出描述 Output Description
一个字符串，先序
样例输入 Sample Input
BADC
BDCA
样例输出 Sample Output
ABCD
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef char ElemType;
typedef struct node
{
ElemType data; //数据元素
struct node *lchild; //指向左孩子结点
struct node *rchild; //指向右孩子结点
} BTNode;
BTNode *CreateBT2(char *post,char *in,int n)
/*post存放后序序列,in存放中序序列,n为二叉树结点个数,
本算法执行后返回构造的二叉链的根结点指针*/
{
BTNode *s;
char r,*p;
int k;
if(n<=) return NULL;
r=*(post+n-); //根结点值
s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s
s->data=r;
for (p=in;p<in+n;p++) //在in中查找根结点
if (*p==r)
break;
k=p-in; //k为根结点在in中的下标
s->lchild=CreateBT2(post,in,k); //递归构造左子树
s->rchild=CreateBT2(post+k,p+,n-k-); //递归构造右子树
return s;
}
void PreOrder(BTNode *b) /*先序遍历的递归算法*/
{
if (b!=NULL)
{
printf("%c",b->data); /*访问根结点*/
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
int main(int argc, char *argv[])
{
freopen("data.in","r",stdin);
char in[],post[];
scanf("%s%s",in,post);
BTNode *root=CreateBT2(post,in,strlen(in));
PreOrder(root);
return ;
}
张泽萱的代码：
#include <iostream>
#include <cstring>
char a[],b[];
using namespace std;
void turn(int l,int r,int st,int ed);
int main(int argc, char *argv[])
{
int n;
cin>>a>>b;//a中序，b后序
n=strlen(b);
turn(,n-,,n-);
return ;
}
void turn(int l,int r,int st,int ed)//l,r分别指向中序的开头和结束，st,ed指向后序的开头和结束
{
int temp,i;
temp=b[ed];
if(l>r||st>ed)return ;
else
{
cout<<char(temp);
for(i=l;i<=r;i++)
{
if(a[i]==temp)
{
turn(l,i-,st,st+i-l-);//查左子树
turn(i+,r,st+i-l,ed-);//查右子树
break;
}
}
}
}