如何根据二叉树 前序遍历 中序遍历 后序遍历 中的两种遍历来反推另一种遍历

时间:2021-01-07 11:25:36

给定任意两种遍历,最关键的一点是要先找到根节点,然后根据根节点划分左右子数的区间范围,然后递归建树。

1.递归的状态参量是  两种遍历的左右端点,也就是有4个状态参量。L1,R1,L2,R2。

2.递归的结束条件,选定其中一种遍历的左端点大于右端点时回溯。也就是递归到了叶子节点了,不能再继续递归了。

3.保存树结构的方法:用Lch[root],来保存root节点的左子节点,Rch[root]来保存root的右子节点

下面上代码:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int N;
int in_order[108], post_order[108];
int lch[108], rch[108];
queue<int> Q;

int build_tree(int L1, int R1,int L2,int R2)
{
    if (L1 > R1)
        return 0;
    int root;
    root = post_order[R2];
    int p = L1;
    while (in_order[p] != root) p++;
    int cnt = p - L1;
    lch[root] = build_tree(L1,p-1,L2,L2+cnt-1);
    rch[root] = build_tree(p + 1, R1, L2 + cnt, R2 - 1);

    return root;
}

int main()
{
    int flag=0;
    scanf("%d", &N);
    for (int i = 1;i <= N;i++)
        scanf("%d", &post_order[i]);
    for (int i = 1;i <= N;i++)
        scanf("%d", &in_order[i]);
    build_tree(1, N, 1, N);
    Q.push(post_order[N]);
    while (!Q.empty())
    {
        int t;
        t = Q.front();
        Q.pop();
        if(!flag)
        printf("%d",t);
        else
        printf(" %d",t);
        flag=1;
        if(lch[t]!=0)
        Q.push(lch[t]);
        if(rch[t]!=0)
        Q.push(rch[t]);
    }
    return 0;
}