首页 > 代码库 > Undraw the Trees (Uva 10562)
Undraw the Trees (Uva 10562)
题意：将多叉树转化为括号表示法。每个结点用除了‘-’, ‘|’, ‘ ’（空格）, ‘#’ 的其他字符表示，每个非叶结点的正下方会有一个 ‘|’ 字符，然后下面是一排 ‘-’ 字符，恰好覆盖所有子节点的上方。单独的一行 ‘#’ 为数据结束。
例样输入：
2
A
|
--------
B C D
| |
----- -
E F G
#
e
|
----
f g
#
例样输出：
(A(B()C(E()F())D(G())))
(e(f()g()))
思路：
将输入数据存入二维数组，在二维数组中进行递归建树。
对于一个结点(r, c)，若 (r+1, c) 这个字符为 ‘|’，则说明存在子树，对其进行递归建树。
确定子结点点的方式为：首先确定 (r+2, c) 这个位置的字符串 “----...” 的范围 left, right,再从(r+3, left), (r+3, right) 这个范围寻找子结点。
核心代码：
void build(int r, int c){ printf("%c", a[r][c]); if(a[r+1][c] == ‘|‘){ //如果该节点有子树 int left=c, right=c; range(left, right, r+2); //传引用，确定字符串 "----..." 的范围 //递归子结点 for(int i=left; i<=right; i++){ if(a[r+3][i]!=‘ ‘ && a[r+3][i]!=‘\0‘ && a[r+3][i]!=‘#‘ && a[r+3][i]!=‘-‘ &&a[r+3][i]!=‘|‘){ //确定该字符是不是结点 build(r+3, i); } } } printf(")");}
结点后面的括号中，为子树。若为叶子结点，则括号中为空。
AC 代码：
/* Undraw the Trees (UVa 10562)*/#include <iostream>#include <cstring>#include <string>using namespace std;const int MAX = 205;char a[MAX][MAX];void input(); //输入 void build(int r, int c); //建立树 void range(int &left, int &right, int r); //确定第 r 行 left(right) 位置 "----..." 字符串的范围。 int main(){ freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T; cin >> T; getchar(); //过滤掉结尾的回车 while(T--){ input(); printf("("); for(int i=0; i<MAX && a[0][i]!=‘\0‘; i++){ if(a[0][i]!=‘ ‘) build(0, i); } printf(")\n"); /*for(int i=0; i<7; i++){ puts(a[i]); } printf("\n");*/ } return 0;}void input(){ int i; memset(a, 0, sizeof(a)); for( i=0; ; i++){ gets(a[i]); if(strcmp(a[i],"#") == 0) break; } a[i][0]=0;} void build(int r, int c){ printf("%c(", a[r][c]); if(a[r+1][c] == ‘|‘){ //如果该节点有子树，则递归建立子树 int left=c, right=c; range(left, right, r+2); //确定字符串 "----..." 的范围 for(int i=left; i<=right; i++){ if(a[r+3][i]!=‘ ‘ && a[r+3][i]!=‘\0‘ && a[r+3][i]!=‘#‘ && a[r+3][i]!=‘-‘ &&a[r+3][i]!=‘|‘){ //如果找到子节点，则递归子节点 build(r+3, i); } } } printf(")");}void range(int &left, int &right, int r){ for(; left>=0 && a[r][left]==‘-‘; left--); left++; for(; right<MAX && a[r][right]==‘-‘; right++); right--;}
Undraw the Trees (Uva 10562)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。