Tree Recovery問題解決レポート

1.構想を解体し、先序中序後序中の頂点の位置を探し、再帰で計算する.
以下は解体構想である:(http://www.cnblogs.com/allensun/archive/2010/11/05/1870214.html)
preorderの最初のノードDがこの木のルートノード、すなわちpostorderの最後の要素です 次に、ノードDをinorderで見つけ、左がABCでルートノードの左サブツリーのinorder、右EFGで右サブツリーinorder 対応するpreorderのBACはそのルートノードの左サブツリーのperorderであり、EGFは右サブツリーpreorderである 再帰的に左右のサブツリーに同様の方法を適用する 
2.再帰関数の書き方を体得する.再帰関数を使用することを決定した後、最初の再帰時の計算順序に対してプログラムを記述し、難点はパラメータの設定である.
3.参照を使用し、constキーを付けて、参照変数が元の変数の値を変更できないことを示します.

#include
#include
#include

using namespace std;

string pre, in;

void Creat_Post(const string &pre, const string &in, string &post, int end)
{
    if (pre == "")
        return;
    post[end] = pre[0];
    unsigned int root = in.find(pre[0]);
    int leftL = root;
    int rightL = pre.size() - leftL - 1;
    Creat_Post(pre.substr(1 + leftL), in.substr(root + 1), post, end - 1);
    Creat_Post(pre.substr(1, leftL), in.substr(0, leftL), post, end - 1 - rightL);
}

int main()
{
    while(cin >> pre >> in)
    {
        int len = pre.size();
        string post(len,'0');
        Creat_Post(pre, in, post, len -1);
        cout << post << endl;
    }
    return 0;
}