2011-06-14 22:09:55Morris
d861. NOIP2001 3.求先序排列
http://zerojudge.tw/ShowProblem?problemid=d861
內容 ：
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
輸入說明
：
第一行为一棵二叉树的中序排列；
第一行为一棵二叉树的后序排列。
輸出說明
：
输出这棵二叉树的前序排列。
範例輸入 ：
BADC BDCA
範例輸出 ：
ABCD
提示
：
出處
：
/**********************************************************************************/
/* Problem: d861 "NOIP2001 3.求先序排列" from NOIP2001普及组第三题 */
/* Language: C */
/* Result: AC (2ms, 223KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 12:39:26 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int pos_tail, top;
char pos[100], in[100], pre[100];
void print(int from, int end) {
int i;
if(from > end) return;
else {
pos_tail--;
for(i = 0; in[i] != '\0'; i++)
if(pos[pos_tail] == in[i]) {
print(i+1, end);
print(from, i-1);
pre[top++] = in[i];
break;
}
}
}
main() {
while(scanf("%s %s",in, pos) == 2) {
pos_tail = strlen(in), top = 0;
print(0, strlen(in)-1);
int i;
for(i = top-1; i >= 0; i--)
printf("%c",pre[i]);
puts("");
}
return 0;
}