poj_2255

题目：

Description

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:

B E

A C G

To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).

Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!

Input

The input will contain one or more test cases.
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
Input is terminated by end of file.

Output

For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).
Sample Input

DBACEGF ABCDEFG
BCAD CBAD
Sample Output

ACBFGED
CDAB

　　分析：根据前序和中序推出后序的题目；拿每一个例子大致模拟下过程：

　　1)根据前序的每一个字母“D”我们可以知道，D一定是整个树的root，而在中序中我们找到"D"的位置，根据中序的遍历我们可得出"D"左边的字母组成了它的左子树，右边的字母组成了它的右子树。

　　2）同样对于左子树“ABC”来说，来说，"B"在前序序列中首先出现，可以判断在这棵子树中“B”是其root,而“A”,"C"则为它的左右子树；对于“D”的右子树“EFG”来说，道理相同, "E“为其root，而其右子树为”FG"，左子树为空，再对"FG"进行判断，前序序列中先出来了”G“可以得出”G“为root，而"F"为其子树；

　　3）根据以上的分析，我们不难画出以下的图形：

将图中的方框加圆替换就可以得到原来的树了；

那现在怎么输入后序序列呢？根据上面的分析我们不难想像可以用递归的方式来解决；分三步走，a)划分问题，就是在前序找到第一个与当前中序序列相等的字母，做为root,它的坐标就是划分左右子树的关键；b）递归分解问题，为两个子树递归调用函数; c)合并问题，对于后序，我们要的是先输出左子树，再输出右子树，最后输出root，所以在两个递归的后面加上一个输出当前root就可以了。同时边界条件为：判断是否是只有一个数据，是的话，就直接输出返回；

代码：

#include<stdio.h>
#include<string.h>

char a[30], b[30];

void getpost(int begin, int end) {

    int pre_len = strlen(a);
    int root_pos, i, j, flag;
    char root;
    if(begin == end) {
        printf("%c", b[begin]);
        return;
    }

    flag = 0;
    //find the first root
    for(i = 0; i < pre_len; ++i) {
        for(j = begin; j <= end;++j) {
            if(a[i] == b[j]) {
                root_pos = j;
                root = b[j];
                flag = 1;
            }
        }
        if(flag == 1)
            break;
    }
    if(root_pos - 1 >= begin)
        getpost(begin, root_pos - 1);
    if(root_pos + 1 <= end) 
        getpost(root_pos + 1, end);
    printf("%c", root);
}

int main() {
    while(scanf("%s%s", a, b) != EOF) {
        getpost(0, strlen(b)-1);
        printf("
");
    }
}