1. 首页
  2. 数据结构

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

二叉树

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

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

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

可以发现,二叉树前序中的第一个节点为树的根节点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;
}

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1031 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

1 条评论

gravatar

  1. 小包子 2016-08-06 Google Chrome 52.0.2743.82Windows 10

    签到成功!签到时间:上午12:38:09每日打卡,生活更精彩哦~

    回复 0楼
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40