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