注意点：

和上一篇的DS Tree 已知先序、中序 => 建树 => 求后序差不多，注意的地方是在aftorder中找根节点的时候，是从右往左找，因此递归的时候注意参数，最好是拿纸和笔模拟一遍。

代码(主体部分)：

/*

    FindRoot函数：根据后序、中序建树

 */

Node* FindRoot(int aft_l, int aft_r, int mid_l, int mid_r)

{

    if (aft_r - aft_l < 0) return NULL;

    Node *root = new Node;

    root -> num = aftorder[aft_r];

    if (aft_l == aft_r)

    {

        root -> l = NULL;

        root -> r = NULL;

        return root;

    }

    int index;

    for (index = mid_l; index <= mid_r; index++)

    {

        if (midorder[index] == aftorder[aft_r]) break;

    }

    root -> r = FindRoot(aft_r-(mid_r-index), aft_r-1, index+1, mid_r);

    root -> l = FindRoot(aft_l, aft_r-(mid_r-index)-1, mid_l, index-1);

    return root;

}

/*

 CalPreorder函数：根据给定的树来计算先序序列

 */

void CalPreorder(Node *head)

{

    if (head == NULL) return ;

    preorder[tot++] = head -> num;

    CalPreorder(head -> l);

    CalPreorder(head -> r);

}

2016/12/21