1. 首页
2. 数据结构
3. 本页

二叉树根据前序中序求后序~~

二叉树

前序遍历顺序: 根节点、左子树、右子树

中序遍历顺序: 左子树、根节点、右子树

后序遍历顺序: 左子树、右子树、根节点

可以发现，二叉树前序中的第一个节点为树的根节点root，然后找出root在中序里面的位置，就可以把前序和中序分别划分为左、右子树两个部分，然后递归调用即可。

举个例子，前序 5 3 2 4 8 6 10 中序 2 3 4 5 6 8 10

首先，5肯定是二叉树的根节点，然后5在中序里面的位置是3号（从0开始），此位置前面的是左子树中的节点，右面的是右子树的节点，即5 || 3 2 4|| 8 2 6 , 2 3 4 || 5 || 6 8 10，对红色的左子树序列、蓝色的右子树序列继续上述过程，直至结束。

已知前序中序求后序：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int MAXN=1100;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

int mid[10500];
int pre[10500];

void solve(int a,int b,int n,bool flag)
{
    if(n==1)    //此时只有一个节点
    {
        cout<<pre[a]<<" ";
        return ;
    }
    if(n<=0)
    {
        return ;
    }
    int pos;               //找到节点
    for(pos=0; pre[a]!=mid[b+pos]; pos++);
    solve(a+1,b,pos,0);       //左子树
    solve(a+pos+1,b+pos+1,n-pos-1,0);  //右
    if(flag)       //根节点
    {
        cout<<pre[a]<<endl;
    }
    else
    {
        cout<<pre[a]<<" ";
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>pre[i];
    }
    for(int i=1; i<=n; ++i)
    {
        cin>>mid[i];
    }
    solve(1,1,n,1);

    return 0;
}

已知后序中序求前序：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int MAXN=1100;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

int mid[10500];
int pre[10500];   //此时为后序

void solve(int a,int b,int n,bool flag)
{
    if(n==1)    //此时只有一个节点
    {
        cout<<" "<<pre[a];
        return ;
    }
    if(n<=0)
    {
        return ;
    }
    if(flag)       //根节点
    {
        cout<<pre[a];
    }
    else
    {
        cout<<" "<<pre[a];
    }
    int pos;               //找到节点
    for(pos=0; pre[a]!=mid[b+pos]; pos++);
    solve(a-n+pos,b,pos,0);       //左子树
    solve(a-1,b+pos+1,n-pos-1,0);  //右

}

int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>pre[i];
    }
    for(int i=1; i<=n; ++i)
    {
        cin>>mid[i];
    }
    solve(n,1,n,1);   //后序最后一点为根

    return 0;
}