資料結構實習 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;
}

           

代碼改變世界