二叉树重构

已知前序中序求后序

//Tree Recovery
#include <iostream>
#include <string>
using namespace std;



void PostOrder(int pre[], int in[], int post[], int left, int right, int&pos, int&index);//构建后序遍历序列
void input(int a[], const int n, string s);//输入
void output(int a[], const int n);//输出
int find(int a[], int left, int right, const int e);//在中序序列中找与先序序列对应的元素的位置

int main()
{
    int length;//序列长度
    int pos = 0;//序列查找的位置
    int index = 0;//构建后序序列的下标
    cout << "length:";
    cin >> length;

    int* in = new int[length];
    int*pre = new int[length];
    int*post = new int[length];

    input(pre, length, "PreOrder:");
    input(in, length, "InOrder:");

    PostOrder(pre, in, post, 0, length - 1, pos, index);
    output(post, length);

    return 0;
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void PostOrder(int pre[], int in[], int post[], int left, int right, int&pos, int&index)
{
    if (left > right)//节点不存在
    {
        return;
    }
    int i = find(in, left, right, pre[pos++]);//查找
    if (i == right && right == left)//叶子结点
    {
        post[index++] = in[i];//加入后续遍历序列中
        return;
    }
    PostOrder(pre, in, post, left, i - 1, pos, index);//递归左子树
    PostOrder(pre, in, post, i + 1, right, pos, index);//递归右子树
    post[index++] = in[i];//插入根节点
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void input(int a[], const int n, string s)
{
    cout << s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
}
void output(int a[], const int n)
{
    cout << "PostOrder:";
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}
int find(int a[], int left, int right, const int e)
{
    for (int i = left; i <= right; i++) {
        if (e == a[i])
            return i;
    }
    return 0;
}