This post is written in Chinese. Please consider using Google Translate

分析：输入二叉树的前序遍历、中序便利，求后序遍历

先建立这棵二叉树，然后递归的输出它的后续遍历即可。问题的关键在于如何建立这棵二叉树。在NOIP初赛中，经常有这样的题目。手算不算难，写成程序实现就需要编程的基本功了。

采取递归的方法建立二叉树。首先取前序遍历的首元素当作二叉树的跟，当前元素为根。把前序遍历中的当前元素当作中序遍历的分割点，中序便利分割点前面的元素一定在当前元素的左子树，分割点后面元素一定在当前元素的右子树。然后加入下一个顶点，再把它当作分割点。如此递归的进行，直到二叉树建立完成。

基本框架

调用 create(0,元素总数-1,根节点);
void create(long L,long R,Node *C)
{
    E=下一个元素();
    if (没有下一个元素)
        return;
    else
    {
        if (E在C左边)
            create(L,分割点-1,C->左子树);
        if (E在C右边)
            create(分割点+1,R,C->右子树);
    }
}

USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: heritage LANG: C++

Compiling... Compile: OK

Executing... Test 1: TEST OK [0.011 secs, 2840 KB] Test 2: TEST OK [0.000 secs, 2840 KB] Test 3: TEST OK [0.000 secs, 2840 KB] Test 4: TEST OK [0.000 secs, 2840 KB] Test 5: TEST OK [0.000 secs, 2844 KB] Test 6: TEST OK [0.000 secs, 2840 KB] Test 7: TEST OK [0.000 secs, 2844 KB] Test 8: TEST OK [0.011 secs, 2844 KB] Test 9: TEST OK [0.000 secs, 2840 KB]

All tests OK.

YOUR PROGRAM ('heritage') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.

/*
ID: cmykrgb1
PROG: heritage
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
class Node
{
public:
    Node()
    {
        left=right=0;
        letter=0;
        position=0;
    }
    Node *left,*right;
    char letter;
    long position;
};
ifstream fi("heritage.in");
ofstream fo("heritage.out");
Node *root;
char fs[26],ms[26];
long cnt=0,cur=1;

void scan(Node *N)
{
    if (N->left) scan(N->left);
    if (N->right) scan(N->right);
    fo << N->letter;
}

void init()
{
    char c;
    int i;
    while (c!=10 && c!=13)
        ms[cnt++]=c=fi.get();
    cnt--;
    while (c==10 && c==13) c=fi.get();
    for (i=0;i<cnt;i++)
        fs[i]=fi.get();
    root=new Node;
    root->letter=fs[0];
    for (i=0;i<cnt;i++)
        if (ms[i]==fs[0])
        {
            root->position=i;
            break;
        }
}

char getnextelement()
{
    if (cur>=cnt)
        return -1;
    else
        return fs[cur++];
}

void create(long L,long R,Node *C)
{
    char E;
    int i;
    bool found;
    while (1)
    {
        found=false;
        E=getnextelement();
        if (E==-1)
            return;
        else
        {
            for (i=L;i<=C->position-1;i++)
                if (ms[i]==E)
                {
                    C->left=new Node;
                    C->left->letter=E;
                    C->left->position=i;
                    create(L,C->position-1,C->left);
                    found=true;
                    break;
                }
            if (!found)
                for (i=C->position+1;i<=R;i++)
                    if (ms[i]==E)
                    {
                        C->right=new Node;
                        C->right->letter=E;
                        C->right->position=i;
                        create(C->position+1,R,C->right);
                        found=true;
                        break;
                    }
            if (!found)
            {
                cur--;
                return;
            }
        }
    }
}

void print()
{
    scan(root);
    fo << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    create(0,cnt-1,root);
    print();
    return 0;
}