【2001年普及组2】求先序排列
/*
已知中序和后序求前序的方法：
#include <stdio.h>
#include <string.h> #define MAX 101 void tryprint(char *s1,char *s2,int st1,int sd1,int st2,int sd2)
{
int i,j ;
printf("%c",s2[sd2]) ;
for(i=st1 ; i<= sd1 ; i++)
if ( s1[i] == s2[sd2])
break ;
if(st1 <= i-1)
tryprint(s1,s2,st1,i-1,st2,st2+i-st1-1) ;
if(i+1 <= sd1)
tryprint(s1,s2,i+1,sd1,sd2-sd1+i,sd2-1);
} int main(void)
{
int len,i,j;
char s1[MAX]={'
Time Limit:1000MS Memory Limit:65536K
Total Submit:208 Accepted:99
Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
Input
一棵二叉树的中序与后序排列
Output
先序排列
Sample Input
BADC BDCA
Sample Output
ABCD
*/
/*
已知中序和后序求前序的方法：
从后序出发，因为后序的最后一个一定是根，然后再从中序中找到对应的根，然后按前序遍列的
方式输出。
技巧： 等分原理，找到中序后就要把中序序列分成两段，左右子树，然后递归进行，分的时候可以
利用求中序的左右子树的结点个数来确定，后序序列的分段
#include <stdio.h>
#include <string.h> #define MAX 101 void tryprint(char *s1,char *s2,int st1,int sd1,int st2,int sd2)
{
int i,j ;
printf("%c",s2[sd2]) ;
for(i=st1 ; i<= sd1 ; i++)
if ( s1[i] == s2[sd2])
break ;
if(st1 <= i-1)
tryprint(s1,s2,st1,i-1,st2,st2+i-st1-1) ;
if(i+1 <= sd1)
tryprint(s1,s2,i+1,sd1,sd2-sd1+i,sd2-1);
} int main(void)
{
int len,i,j;
char s1[MAX]={'