九度OJ 1078二叉木遍歴

タイトルアドレス:http://ac.jobdu.com/problem.php?pid=1078
 
タイトルの説明:
二叉木の前序、中序、後序遍歴の定義:前序遍歴:いずれかのサブツリーに対して、先にフォローにアクセスし、それからその左サブツリーを遍歴し、最後にその右サブツリーを遍歴する.中序遍歴:いずれかのサブツリーに対して、まず左サブツリーを遍歴し、それからルートにアクセスし、最後に右サブツリーを遍歴する.≪後順ループ|Back Sequence Rolling|emdw≫:いずれかのサブツリーに対して、左サブツリーをループし、右サブツリーをループし、最後にルートにアクセスします.1本の二叉木の前序遍歴と中序遍歴を与え、後序遍歴を求める(ヒント:与えられた前序遍歴と中序遍歴は後序遍歴を一意に決定することができる).
入力:
2つの文字列は、長さnが26以下である.第1の動作の前順序は遍歴し、第2の動作の中で順序は遍歴する.ツリーのノード名は大文字でA,B,C....最大26個です.
出力:
入力サンプルには複数のグループがあり、各グループのテストサンプルに対して、1行を出力し、後順に遍歴する文字列とします.
サンプル入力:

ABC

BAC

FDXEAG

XDEFAG

サンプル出力:

BCA

XEDGAF

ツリーの再構築
 
 

/*

 * Main.c

 *

 *  Created on: 2014 1 27 

 *      Author: Shaobo

 */

#include <stdio.h>

#include <string.h>

 

void to_post(char pre[], char in[], char post[], int len){

    int i;

 

    if (len <= 0)

        return;

 

    for (i=0; i<len; ++i)

        if (in[i] == pre[0])

            break;

    post[len-1] = pre[0];

    to_post (pre+1, in, post, i);

    to_post (pre+i+1, in+i+1, post+i, len-i-1);

}

 

int main(void){

    char pre[30], in[30], post[30];

    int len;

 

    while (scanf ("%s", pre) != EOF){

        scanf ("%s", in);

        len = strlen (pre);

        to_post (pre, in, post, len);

        post[len] = '\0';

        printf ("%s
", post);

    }

 

    return 0;

}