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;
}