数据结构实习 problem L 由二叉树的中序层序重建二叉树

由二叉树的中序层序重建二叉树

writer：pprp

用层序中序来重建二叉树

代码点这里

其实本质上与前序中序建立二叉树没有什么太大区别

大概思路：

递归解法，对当前层进行处理，通过层序遍历可以得到当前的根节点，然后在中序遍历中找到该节点，对左右两边的内容进行分析，理想情况下应该是可以递归进行下去，找到左子树的中序遍历和层序遍历，找到右子树的中序遍历和层序遍历，然后进行递归，但是可以发现，层序遍历是交错的，所以是需要重新处理以后才能进行递归

现在只要通过处理得到左子树右子树的层序遍历序列就好了，通过两层循环找到在左子树中出现的元素在层序遍历中出现的顺序，并将其存储在新开的数组中，然后就可以继续递归下去了

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 10000;

struct tree

{

    tree * l, *r;

    int data;

    tree()

    {

        l = r = NULL;

        data = 0;

    }

};

int layer[maxn], in[maxn];

//前序遍历

void PreOrder(tree * root)

{

    if(root != NULL)

    {

        cout << root->data << " ";

        PreOrder(root->l);

        PreOrder(root->r);

    }

}

//后序遍历

void PostOrder(tree * root)

{

    if(root != NULL)

    {

        PostOrder(root->l);

        PostOrder(root->r);

        cout << root->data << " ";

    }

}

//从 0 开始

tree * CreateTree(int * layer, int * in, int t)

{

    if(t == 0) return NULL;

    int Llayer[maxn], Rlayer[maxn];

    int Lin[maxn], Rin[maxn];

    tree * node = new tree;

    node->data = layer[0];

    //find the place of the root

    int i;

    for(i = 0; i < t; i++)

        if(in[i] == layer[0])

            break;

    //in order

    int cnt = 0;

    for(int j = 0; j < i ; j++)

        Lin[cnt++] = in[j];

    cnt = 0;

    for(int j = i+1; j < t; j++)

        Rin[cnt++] = in[j];

    cnt--;

    //layer order

    int Llayercnt = 0;

    int Rlayercnt = 0;

    for(int j = 1; j < t ; j++)

        for(int k = 0 ; k < i ; k++)

            if(layer[j] == in[k])

                Llayer[Llayercnt++] = layer[j];

    for(int j = 1; j < t; j++)

        for(int k = i ; k < t; k++)

            if(layer[j] == in[k])

                Rlayer[Rlayercnt++] = layer[j];

    node->l = CreateTree(Llayer,Lin,Llayercnt);

    node->r = CreateTree(Rlayer,Rin,Rlayercnt);

    return node;

}

int main()

{

    int n;

    cin >> n;

    for(int i = 0 ; i < n ; i++)cin >> layer[i];

    for(int i = 0 ; i < n ; i++)cin >> in[i];

    tree * root;

    root = CreateTree(layer,in,n);

    PreOrder(root);

    cout << endl;

    PostOrder(root);

    return 0;

}