总算学到树了，是道BFS的题。可以用指针+结构体，但是不喜欢，所以按书上的改成了数组。思路和书上的一样。
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
| #include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=550;
const int root=1;
int cnt,left[maxn],right[maxn],value[maxn];
bool failed,have_value[maxn];
char s[maxn];
vector<int>a;
void new_tree(){
left[root]=right[root]=0;
have_value[root]=false;
cnt=root;
return;
}
int newnode(){
int u=++cnt;
left[u]=right[u]=0;
have_value[u]=false;
return u;
}
void addnote(int v,char* s){
int n=(int)strlen(s);
int u=root;
for(int i=0;i<n;i++)
if(s[i]=='L'){
if(!left[u]) left[u]=newnode();
u=left[u];
}
else if(s[i]=='R'){
if(!right[u]) right[u]=newnode();
u=right[u];
}
if(have_value[u]) failed=true;
value[u]=v;
have_value[u]=true;
return;
}
bool read_input(){
failed=false;
for(;;){
if(scanf("%s",s)!=1) return false;
if(!strcmp(s,"()")) break;
int v;
sscanf(&s[1],"%d",&v);
addnote(v,strchr(s,',')+1);
}
return true;
}
bool bfs(){
if(failed) return false;
queue<int>q;
a.clear();
q.push(root);
while(!q.empty()){
int u=q.front();
q.pop();
if(!have_value[u]) return false;
a.push_back(value[u]);
if(left[u]) q.push(left[u]);
if(right[u]) q.push(right[u]);
}
return true;
}
void print(){
for(int i=0;i<a.size();i++){
if(i) printf(" ");
printf("%d",a[i]);
}
printf("\n");
return;
}
int main(){
while(1){
new_tree();
if(!read_input()) break;
if(!bfs()) failed=true;
if(failed) printf("not complete\n");
else print();
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **