Uva122-二叉树构建与层次遍历

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

根据输入构建一颗二叉树并输出层次遍历的结果，二叉树的构建有结构体和数组两种形式。

链接

Uva122-Trees on the level

题目描述

以一组$(n, s)$的形式给定一棵二叉树，其中$n$是从根节点出发以$s$为路径到达的节点的权值。要求输出这棵二叉树的层次遍历结果。

题解

层次遍历直接用$BFS$就可以得到。关键是构建出二叉树，构建二叉树的方式有两种：一种是采用动态结构，即以结构体来表示一个节点，储存这个节点的权值、左右子树的信息；另一种是采用静态结构，即用数组来储存节点信息，例如$val[maxn]$，$left[maxn]$，$right[maxn]$分别存储节点的权值和左右子树信息。

代码

动态结构

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
 *
 * Author : Aincrad
 *
 * Date : Thu 20 Sep 22:23:49 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 307;
char s[maxn];
bool failed;

struct Node{
    int v;
    Node *left, *right;
    bool h_val;
    Node():left(NULL), right(NULL), h_val(false){}; 
};

Node* root;

void addnode(char* s, int v){
    int n = strlen(s);
    Node* u = root;
    for(int i = 0; i < n - 1; i++){
        if(s[i] == 'L'){
            if(u->left == NULL) u->left = new Node();
            u = u->left;
        }
        else if(s[i] == 'R'){
            if(u->right == NULL) u->right = new Node();
            u = u->right;
        }
    }
    if(u->h_val) failed = true;
    u->v = v;
    u->h_val = true;
}

bool read_input(){
    int v;
    failed = false;
    root = new Node();
    while(1){
        if(scanf("%s", s) == EOF) return false;
        if(strcmp(s, "()") == 0) break;
        sscanf(s + 1, "%d", &v);
        addnode(strchr(s, ',') + 1, v);
    }
    return true;
}

void bfs(){
    vector<int> vec;
    queue<Node*> que;
    que.push(root);
    while(!que.empty()){
        Node* u = que.front();
        que.pop();
        if(!u->h_val){
            cout << "not complete" << endl;
            return;
        }
        vec.push_back(u->v);
        if(u->left != NULL) que.push(u->left);
        if(u->right != NULL) que.push(u->right);
    }
    for(size_t i = 0; i < vec.size(); i++){
        if(i == 0) cout << vec[i];
        else cout << " " << vec[i];
    }
    cout << endl;
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    while(1){
        if(read_input()){
            if(failed) cout << "not complete" << endl;
            else bfs();
        }
        else{
            break;
        }
    }
    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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
 *
 * Author : Aincrad
 *
 * Date : Fri 21 Sep 14:10:14 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 307;
int leftt[maxn], rightt[maxn], val[maxn];
bool h_val[maxn], failed;
char s[maxn];
int root, cnt;

void bfs(){
    vector<int> vec;
    queue<int> que;
    que.push(root);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        if(!h_val[v]){
            cout << "not complete" << endl;
            return;
        }
        vec.push_back(val[v]);
        if(leftt[v]) que.push(leftt[v]);
        if(rightt[v]) que.push(rightt[v]);
    }
    for(size_t i = 0; i < vec.size(); i++){
        if(i == 0) cout << vec[i];
        else cout << " " << vec[i];
    }
    cout << endl;
}

void addnode(char* s, int v){
    int n = strlen(s);
    int u = root;
    for(int i = 0; i < n - 1; i++){
        if(s[i] == 'L'){
            if(leftt[u] == 0){
                cnt++;
                leftt[u] = cnt;
            }
            u = leftt[u];
        }
        else if(s[i] == 'R'){
            if(rightt[u] == 0){
                cnt++;
                rightt[u] = cnt;
            }
            u = rightt[u];
        }
    }
    if(h_val[u]) failed = true;
    val[u] = v;
    h_val[u] = true;
}

bool read_input(){
    memset(h_val, false, sizeof(h_val));
    memset(leftt, 0, sizeof(leftt));
    memset(rightt, 0, sizeof(rightt));
    int v;
    root = 1;
    cnt = 1;
    failed = false;
    leftt[root] = 0, rightt[root] = 0; 
    while(1){
        if(scanf("%s", s) == EOF) return false;
        if(strcmp(s, "()") == 0) break;
        sscanf(s + 1, "%d", &v);
        addnode(strchr(s, ',') + 1, v);
    }
    return true;
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    while(1){
        if(read_input()){
            if(failed) cout << "not complete" << endl;
            else bfs();
        }
        else
            break;
    }
    
    return 0;
}