UVa 10562 看图写树
来源：程序员人生 发布时间：2014-09-04 05:53:41 阅读次数：2475次
题目：题目就是给出一幅ASCII字符构成的树的图，然后转换成由字符括号构成的树的表示形式。可以知道，树有孩子结点的话，正下方会有一个字符 '|' ，紧接着会有一个覆盖所有孩子结点的字符序列“-------”，然后其下就是孩子结点。
思路：先将所有数据读下来。然后递归处理，给定一个左右边界，在该边界内逐个检查字符，如果是结点字符，则判断有无孩子等后续处理。
注意：因为每行会有空格，所以不能用scanf输入，换成fgets的话会保留有换行符（当然，可以进行处理或后续判断），这里使用的是gets来读入，因为可以确保不会溢出。
另外，由scanf改为gets后需要在读第一个整数后来个getchar弃掉换行符。发现每次改输入时都容易有这个问题，下次改输入时要注意。gets和scanf搭配时要注意换行符的问题。
另外，这里不要认为字符串每次都会重新读入，就不用memset初始化了；如果新的数据行数比旧的少，残留的数据还是可能影响到的，因为你有检查h+1和h+2而且没有对其是否超过总行数进行判断。
另外，由于数组中其他字符为' '，所以在判断是否为结点字符时加入了不等于空字符这一项。（当然，你可以通过给定的是严格的左右范围，来处理空字符这个问题）
吐槽：由于没把freopen注释掉，导致WA了，还以为是加入不等于空字符导致的~~
递归是个好东西，最近几次写的比较多~
终于做完二叉树小专题的了~感觉比做线性表的还快一点啊~
Code：
#include<stdio.h>
#include<string.h>
#define MAXN 210
void dfs(int h,int left,int right);
char tree[MAXN][MAXN];
int main()
{
//freopen("10562.in","r",stdin);
//freopen("10562.out","w",stdout);
int t;
scanf("%d",&t);
getchar();//弃了换行符，不是在while内。。
while(t-->0)
{
int hs=0;
memset(tree,0,sizeof(tree));//不要认为有gets输入了就不memset了，旧数据有可能影响到。
while(gets(tree[hs])!=NULL && tree[hs++][0]!='#');
dfs(0,0,MAXN);
printf("
");
}
return 0;
}
void dfs(int h,int left,int right)
{
printf("(");
for(int i=left;i<right;++i)
{
char c=tree[h][i];
if(c!='-' && c!='|' && c!=' ' && c!='#' && c!=' ')
{//是一结点字符
printf("%c",c);
if(tree[h+1][i]=='|')
{//有孩子
int x=i-1;
while(tree[h+2][x]=='-') x--;
//x++; //不需要这句，因为for循环中是<right，不是小于等于
int y=i+1;
while(tree[h+2][y]=='-') y++;
//y--;
dfs(h+3,x,y);
}
else printf("()");//printf("%c:()",c);
}
}//for
printf(")");
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
