前序/中序--->后序

参考：http://www.cnblogs.com/rain-lei/p/3576796.html

！！由前序和后序序列无法确定二叉树

preOrder 5 3 2 4 8 6 9   midOrder 2 3 4 5 6 8 9  postOrder 2 4 3 6 9 8 5

#include <iostream>

using namespace std;

const int maxn = ;

typedef struct Node

{

    int key;

    struct Node *left;

    struct Node *right;

}treeNode;

int preOrder[maxn];

int midOrder[maxn];


// 由中序和后序序列创建树

treeNode *createTree(int preLeft, int preRight, int midLeft, int midRight)

{

    if (preRight - preLeft < ) return NULL;

    treeNode *root = new treeNode;

    root->key = preOrder[preLeft];

    if (preRight == preLeft)

    {

        root->left = NULL;

        root->right = NULL;

    }

    int index;

    for (index = midLeft; index <= midRight; ++index)

    {

        if (midOrder[index] == preOrder[preLeft]) break;

    }

    root->left = createTree(preLeft + , preLeft + (index - midLeft), midLeft, index - );

    root->right = createTree(preLeft + (index - midLeft) + , preRight, index + , midRight);

    return root;

}

void postOrder(treeNode *root)

{

    if (root != NULL)

    {

        postOrder(root->left);

        postOrder(root->right);

        cout << root->key << " ";

    }

}

int main()

{

    int n;

    cout << "Input the number of Node: " << endl;

    cin >> n;

    cout << "The preOrder: " << endl;

    for (int i = ; i < n; ++i)

        cin >> preOrder[i];

    cout << "The midOrder: " << endl;

    for (int i = ; i < n; ++i)

        cin >> midOrder[i];

    treeNode *root = createTree(, n - , , n - );

    cout << "The postOrder: " << endl;

    postOrder(root);

    cout << endl;

    system("pause");

    return ;

}