POJ 2255 Tree Recovery 解题报告

一、问题描述

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:

                                               D

                                              / \

                                             /   \

                                            B     E

                                           / \     \

                                          /   \     \

                                         A     C     G

                                                    /

                                                   /

                                                  F

 

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

 

二、解题思路

先拿示例来分析吧，然后再抽象出一个方法。示例中的前序DBACEGF，中序ABCDEFG，那么可知前序序列第一个字符D为该树的根节点，也就是说D为后序遍历的最后一个节点。再看中序的ABCDEFG，可知ABC为中序遍历左子树节点序列，EFG为中序遍历右子树节点。再对比一下此时的前序序列DBACEGF，BAC为前序遍历左子树地序列，EGF为前序遍历右子树的序列。那么问题就变为分别求左右子树的后序遍历序列了。再用上面方法分别求解。

前序为BAC，中序为ABC的后序序列

前序为EGF，中序为EFG的后序序列

D

用char p[]保存前序序列,char m[]保存中序序列， char h[]来保存后序序列。定义函数void FindPost(int ps,int pt,int ms,int mt)，该函数递归地找出前序序列为p[ps,ps+1,...,pt]，后序序列为m[ms,ms+1,....,mt]的后序序列h[]。后序序列先找到的是最后一个，然后是倒数第2个，依次找到第一个，定义一个变量len保存当前找到的是哪一个，初值为len=N，N为序列的长度。

三、代码

 

#include<iostream>
#include<string>
using namespace std;
char p[28];//perorder
char m[28];//inorder
char h[28];//postorder
int N;
int len;
//从str[s,s+1,...,t]中找到第一个字符c的位置
int Find(char str[], int s,int t,char c)
{
    for(int i=s;i<=t;++i)
    {
        if(str[i]==c)
            return i;
    }
    return -1;
}
//递归找出前序序列为p[ps,ps+1,...,pt]，后序序列为m[ms,ms+1,....,mt]的
//后序序列，后序序列保存在h[]中
void FindPost(int ps,int pt,int ms,int mt)
{
    if(ps>pt || ms >mt)
        return ;
    if(ps==pt)
    {
        len--;    
        h[len]=p[ps];
        return ;
    }
    else
    {
        int mid=Find(m,ms,mt,p[ps]);
        len--;
        h[len]=p[ps];
        FindPost(pt-mt+mid+1, pt, mid+1,mt);
        FindPost(ps+1, ps+mid-ms, ms,mid-1);
    }
}
int main()
{
    while(cin>>p>>m)
    {    
        N=strlen(p);
        len=N;
        h[N]='\0';
        FindPost(0,N-1,0,N-1);
        cout<<h<<endl;
    }
    return 0;
}