• 欢迎光临~

# 6.5 竞赛题目选讲

Undraw_the_Trees

``````#include<iostream>
#include<vector>
using namespace std;

const int maxn = 20000+5, maxl = 200+5;
int cnt = 0, sum = 0;
string tree[maxl];

struct Node{
string name;
vector<Node*> v;
} node[maxn];

Node* build(int p, int s, int e, string name) {
Node* root = &node[cnt++];
root->v.clear();
root->name = name;
if(p >= sum) return root;
for(int i = s; i < e; i++) {
if(tree[p][i] != ' ' && tree[p][i] != '#' && tree[p][i] != '-' && tree[p][i] != '|') {
name = tree[p][i];
if(p+1 < sum && tree[p+1][i] == '|') {
int ts, te;
for(ts=i, te=i; ; ) {
if(ts > -1 && tree[p+2][ts-1]=='-') ts--;
else if(te < tree[p+2].length() && tree[p+2][te+1]=='-') te++;
else break;
}
if(te > tree[p+3].length()-1) te = tree[p+3].length()-1;
root->v.push_back(build(p+3, ts, te+1, name));
}else{
root->v.push_back(build(p+3, -1, -1, name));
}
}
}
return root;
}

void print_tree(Node* root) {
cout << root->name;
cout << "(";
for(int i = 0; i < root->v.size(); i++) print_tree(root->v[i]);
cout << ")";
}

int main() {
//	freopen("test.in", "r", stdin);
//	freopen("test.out", "w", stdout);
int t;
cin >> t;
while(t--) {
cnt = sum = 0;
string line;
while(getline(cin, line) && line != "#") {
tree[sum++] = line;
}
string name = " ";
int pos = 0;
for(; pos < sum; pos++) {
for(int i = 0; i < tree[pos].length(); i++)
if(tree[pos][i] != ' ') {
name = tree[pos][i];
break;
}
if(name != " ") break;
}
Node* root = build(pos+3, 0, tree[pos+3].length(), name);
cout << "(";
if(name != " ") print_tree(root);
cout << ")";
cout << endl;
}
return 0;
}
``````

``````#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

const int maxn = 200 + 10;
int n;
char buf[maxn][maxn];

//递归遍历并且输出以字符buf[r][c]为根的树
void dfs(int r, int c) {
printf("%c(", buf[r][c]);
if(r+1 < n && buf[r+1][c] == '|') { //有子树
int i = c;
while(i-1 >= 0 && buf[r+2][i-1] == '-') i--;//找“----”的左边界
while(buf[r+2][i] == '-' && buf[r+3][i] != '') {
if(!isspace(buf[r+3][i])) dfs(r+3, i);//fgets读入的'n'也满足isspace()//空白符指空格、水平制表、垂直制表、换页、回车和换行符,isspace函数的作用就是判断是否是空白符
i++;
}
}
printf(")");
}
/*

fgets读取到n的时候会结束，如果此时还没有到n-1个字符，那么他会存储，也就是说fgets只是以n作为终止条件之一，并不是其不会读取换行符，

*/
void solve() {
n = 0;
for(;;) {
fgets(buf[n], maxn, stdin);
if(buf[n][0] == '#') break; else n++;
}
printf("(");
if(n) {
for(int i = 0; i < strlen(buf[0]); i++)
if(buf[0][i] != ' ') { dfs(0, i); break; }
}
printf(")n");
}

int main() {
int T;
fgets(buf[0], maxn, stdin);
sscanf(buf[0], "%d", &T);
while(T--) solve();
return 0;
}
``````