二叉树中序和后序遍历->层序和先序遍历

发表于 | 分类于 | | 阅读次数:

给定一个二叉树的中序遍历和后序遍历求出其层序遍历和先序遍历。

建成一棵二叉树

1
2
3
4
5
6
7
8
9
10
11
12
int in_order[maxn], post_order[maxn], lch[maxn], rch[maxn];
//把in_order[l1...r1]和post_order[l2...r2]建成一棵二叉树，返回树根
int build(int l1, int r1, int l2, int r2){
    if(l1 > r1) return 0;
    int v = post_order[r2];
    int pos = 0;
    while(in_order[pos] != v) pos++;
    int len = pos - l1;
    lch[v] = build(l1, l1 + len - 1, l2, l2 + len - 1);
    rch[v] = build(l1 + len + 1, r1, l2 + len, l2 - 1);
    return v;
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 *
 * Author : Aincrad
 *
 * Date : Fri 21 Sep 21:39:43 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 107;
int in_order[maxn], post_order[maxn];
string line;
int n;
vector<int> vec[maxn];

void read(int* s){
    getline(cin, line);
    stringstream ss;
    ss.str(line);
    n = 0;
    int x;
    
    while(ss >> x){
        s[n++] = x;
    }
}

int findd(int x){
    int i;
    for(i = 0; i < n; i++){
        if(in_order[i] == x) break;
    }
    return i;
}

void build(int l1, int r1, int l2, int r2, int l){
    if(l1 > r1) return;
    int v = post_order[r2];
    vec[l].push_back(v);
    int pos = findd(v);
    int len = pos - l1;
    build(l1, l1 + len - 1, l2, l2 + len - 1, l + 1);
    build(l1 + len + 1, r1, l2 + len, r2 - 1, l + 1);
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    read(in_order);
    read(post_order);
    build(0, n - 1, 0, n - 1, 0);
    
    for(int i = 0; i < n; i++){
        for(size_t j = 0; j < vec[i].size(); j++){
            if(i == 0 && j == 0) cout << vec[i][j];
            else cout << " " << vec[i][j];
        }
    }
    cout << endl;
    return 0;
}

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
 *
 * Author : Aincrad
 *
 * Date : Fri 21 Sep 21:39:43 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 107;
int in_order[maxn], post_order[maxn];
string line;
int n;
vector<int> vec;

void read(int* s){
    getline(cin, line);
    stringstream ss;
    ss.str(line);
    n = 0;
    int x;
    
    while(ss >> x){
        s[n++] = x;
    }
}

int findd(int x){
    int i;
    for(i = 0; i < n; i++){
        if(in_order[i] == x) break;
    }
    return i;
}

void build(int l1, int r1, int l2, int r2){
    if(l1 > r1) return;
    int v = post_order[r2];
    vec.push_back(v);
    int pos = findd(v);
    int len = pos - l1;
    build(l1, l1 + len - 1, l2, l2 + len - 1);
    build(l1 + len + 1, r1, l2 + len, r2 - 1);
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    read(in_order);
    read(post_order);
    build(0, n - 1, 0, n - 1);
    for(size_t i = 0; i < vec.size(); i++){
        if(i == 0) cout << vec[i];
        else cout << " " << vec[i];
    }
    cout << endl;
    return 0;
}