UVa 712 - S-Trees

二叉树的题,建树之后代数就行。

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
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
int n,m,t,x[8];
struct Node{
Node *left,*right;
bool have_value;
int v;
Node():v(0),have_value(false),left(NULL),right(NULL){}
};
vector<Node*>tree[8];
Node* root;
void read_order(){
string s;
getline(cin,s);
stringstream ss(s);
for(int i=0;i<n;i++){
ss.get();
ss>>x[i];
ss.get();
}
}
Node* newnote(){
return new Node();
}
void build(vector<Node*>a,int b){
for(int i=0;i<a.size();i++){
a[i]->left=newnote();
a[i]->right=newnote();
tree[b+1].push_back(a[i]->left);
tree[b+1].push_back(a[i]->right);
}
return;
}
void remove_tree(Node* u){
if(u==NULL) return;
remove_tree(u->left);
remove_tree(u->right);
delete u;
}
int main(){
while(cin>>n&&n){
cin.get();
string s,s0,sk,empty;
read_order();
cin>>s;
root=newnote();
tree[0].push_back(root);
for(int i=0;i<n;i++){
build(tree[i],i);
}
for(int i=0;i<tree[n].size();i++){
tree[n][i]->v=s[i];
tree[n][i]->have_value=true;
}
cin>>m;
while(m--){
cin>>s0;
s=empty;
Node *t=root;
for(int i=0;i<n;i++)
s+=s0[x[i]-1];
s0=s;
for(int i=0;i<n;i++){
if(s0[i]=='0') t=t->left;
else t=t->right;
}
sk+=t->v;
}
cout<<"S-Tree #"<<++t<<":"<<endl;
cout<<sk<<endl;
cout<<endl;
for(int i=0;i<8;i++) tree[i].clear();
remove_tree(root);
memset(x,0,sizeof(x));
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。