分析：輸入二叉樹的前序遍歷、中序便利，求後序遍歷

先建立這棵二叉樹，然後遞歸的輸出它的後續遍歷即可。問題的關鍵在於如何建立這棵二叉樹。在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;
}