后序、中序得前序、层序

后序、中序得前序、层序

输入

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出

4 1 6 3 5 7 2

两种方法：

1.第一种编程较为复杂，但是思路清晰，而且通用。
建树+BFS

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>


using namespace std;

const int maxn=50;

struct node{

    int data;
    node* lchild;
    node* rchild;



};


int pre[maxn],in[maxn],post[maxn];

int n;


node* create(int postL,int postR,int inL,int inR )
{
    if(postL>postR || inL>inR)
    {
        return NULL;
    }


    node* root = new node;

    root->data=post[postR];

    int k=-1;

    for(int i=inL;i<=inR;i++)
    {
        if(in[i]==post[postR])
        {

            k=i;
            break;
        }
    }

    int num_left=k-inL;

    root->lchild=create(postL,postL+num_left-1,inL,k-1);

    root->rchild=create(postL+num_left,postR-1,k+1,inR);


    return root;








}



void BFS(node* root)
{

    int num=0;

    queue<node* > q;

    q.push(root);

    while(!q.empty())
    {
        node* now=q.front();
        q.pop();


        printf("%d",now->data);


        num++;
        if(num<n)
        {
            printf(" ");


        }

        if(now->lchild!=NULL)
        {
            q.push(now->lchild);
        }

        if(now->rchild!=NULL)
        {
            q.push(now->rchild);
        }


    }





}



int main()
{

    scanf("%d",&n);


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

        scanf("%d",&post[i]);
    }

    for(int i=0;i<n;i++)
    {
        scanf("%d",&in[i]);

    } 

    node* root=create(0,n-1,0,n-1);

    BFS(root);





    return 0;
}

2.第二种，直接输出不建树

1>.中序+后序-》前序

/*因为后序的最后一个总是根结点，令i在中序中 
//找到该根结点，则i把中序分为两部分，左边为 
//左子树，右边为右子树。因为是输出先序（根左右）, 
//所以先打印出当前根结点，然后打印左子树， 
//再打印右子树。左子树在后序中的根结点为 
//root-(end-i+1),就是当前根结点-右子树的个数。 
//左子树在中序中的起始点start为start，末尾end点 
//为i-1,右子树的根结点为当前根结点的前一个结点 
//root-1,右子树的起始点start为i+1,末尾end点为end。 
*/


#include <cstdio> 
#include <algorithm>


using namespace std;

int post[]={3,4,2,6,5,1};

int in[]={3,2,4,1,6,5};


void pre(int root,int start,int end)
{
    if( start>end )
    {
        return;

    }

    int i=start;
    while(i<end && in[i]!=post[root])
    {
        i++;
    }


    printf("%d ",post[root]);
    pre(root-1-end+i,start,i-1);
    pre(root-1,i+1,end);



}


int main()
{
    pre(5,0,5);

    return 0;
}

2>.中序+后序-》层序

/*与后序中序转换为前序的代码相仿（无须构造二叉树
//再进行广度优先 搜索） 
//多加一个变量index，表示当前的根结点在二叉搜索树 
//中对应的下标（从0开始），所以进行一次输出先序的 
//递归的时候，就可以把根结点下标所对应的值存储在 
//level数组中（开始把level都置为-1，表示此处没有
//结点），这样在递归完成后level数组中非-1的数就是 
//按照下标排列的层序遍历的顺序 
//
//
//
*/


#include <cstdio> 
#include <vector>

using namespace std;

vector<int> post,in,level(100000,-1);

void pre(int root,int start,int end,int index)
{
    if(start>end)
    {
        return;
    }

    int i=start;
    while(i<end && in[i]!=post[root])
    {
        i++;
    }

    level[index]=post[root];
    pre(root-1-end+i,start,i-1,2*index+1);
    pre(root-1,i+1,end,2*index+2);





}

int main()
{

    int n,cnt=0;

    scanf("%d",&n);

    post.resize(n);

    in.resize(n);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&post[i]);
    }

    for(int i=0;i<n;i++)
    {
        scanf("%d",&in[i]);
    }

    pre(n-1,0,n-1,0);

    for(int i=0;i<level.size();i++)
    {
        if(level[i]!=-1&& cnt!=n-1)
        {
            printf("%d ",level[i]);
            cnt++;
        }
        else if( level[i]!=-1)
        {
            printf("%d",level[i]);
            break;

        }
    }

    return 0;
}