UVa 10562：Undraw the Trees （不限制儿子个数的树）

UVa 10562：Undraw the Trees （不限制儿子个数的树）2014-10-06 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=1503

题目类型：数据结构，二叉树

输入与输出：

Sample Professor’s Trees2A

--------

B C D

| |

----- -

E F G

----

f g

#
Corresponding Our Trees

（A（B（）C（E（）F（））D（G（））））

（e（f（）g（）））

题目大意：

左边的输入表示的是一棵树，这棵树的一个结点可以有很多个儿子。所有的输入，只要是可打印的字符，并且不是空格， ‘#’，’|‘， ’-‘的都是代表一个节点。

如果一个结点下方有‘|’则代表他有儿子。他的儿子们在一段连续‘-’的下面的结点。

分析与总结：

如果用建树的方法，初看可能比较复杂，但是其实是很并不难的。我的方法是构造一个有MAXN个儿子指针的结点，然后开一个和最大的输入尺寸一样的二维数组存结点，分别相对应

于输入的二维字符串数组。

然后对输出进行枚举，当碰到一个是结点的字符时，就对结点数组相对应结点找儿子，找儿子用一个函数实现，向下搜索出它的所有儿子即可。

最后构造完之后，对这棵树进行前序遍历输出，注意输出左右括号的位置。

按理说这题只要并不难的，但是却被恶心到了，昨天晚上开始做的，想好思路后很快就敲好代码，过了样例之后自信满满的提交了，然后，看到了血红血红的Wrong answer，给了我当头一棒。之后就不断的调试，不断的WA。

然后就在网上找测试样例，结果发现也全部都可以过。这就说明一定不是我思路的问题，肯定是一些细节或者边界条件没考虑到。

百度，谷歌被我翻了几十页，结果发现网上的解题报告全部都是用递归搜索解的，而且完全没有和我解题思路一样的。更奇葩的是，我的队友也想了一个很奇葩的方法，结果我们两个都卡了很久。

不断的WA，血淋淋的事实，说明即使你认为自己是对的，确保是万无一失的，也可能会有一些恶心的边界或者自己的思维漏洞而wa。

#include<cstdio>#include<cctype>#include<iostream>#include<cstring>#define MAXN 205using namespace std; class Node{public:char data;Node *son[MAXN];}; Node *root;Node node[210][210];char str[210][210];int row; inline bool isNode（char ch）{if（isprint（ch） && ch！="-" && ch！="|" &&ch！=" " && ch！="#"）return true;return false;} void linkSon（int r, int c）{if（r+3 >= row || str[r+1][c]！="|"） return;int i,j;// 移动到有 ‘-’ 的最左边for（i=c; str[r+2][i]=="-"&&i>=0; --i） ;;int sonNum=0;i++;// 从最左边的‘-’往右枚举到最右边的"-".// 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45528.htm//这里特别要注意边界条件，就因为这个i<strlen（str[r+2]）&&i<strlen（str[r+3]）// 导致我郁闷了一个晚上+一个早上for（ ; str[r+2][i]=="-"&&i<strlen（str[r+2]）&&i<strlen（str[r+3]）; ++i）{if（isNode（str[r+3][i]））{ // 如果是结点，链接起来node[r][c].son[sonNum++] = &node[r+3][i];}}} void dfs（Node *root）{if（root）{printf（"%c", root->data）;bool flag = true;for（int j=0; j<MAXN; ++j）{if（root->son[j]！=NULL）{flag = false;if（j==0） printf（"（"）;dfs（root->son[j]）;}}if（flag） printf（"（）"）;else printf（"）"）;}}void Solve（）{// 初始化for（int i=0; i<row; ++i）{for（int j=0; j<strlen（str[i]）; ++j）{for（int k=0; k<MAXN; ++k）node[i][j].son[k] = NULL; }} root = NULL;for（int i=0; i< row; ++i）{for（int j=0; j<strlen（str[i]）; ++j）{if（isNode（str[i][j]））{if（root==NULL）{node[i][j].data = str[i][j];root = &node[i][j];linkSon（i,j）;break;}else{node[i][j].data = str[i][j];linkSon（i, j）;}}}} printf（"（"）;dfs（root）;printf（"）
"）;} int main（）{ // freopen（"input.txt", "r", stdin）;int T;scanf（"%d%*c", &T）;while（T--）{row=3;memset（str[2], 0, sizeof（str[2]））;while（gets（str[row]））{if（str[row][0]=="#"） break;++row;memset（str[row], 0, sizeof（str[row]））;// 初始化，避免遗留上次的数据下来}Solve（）;}return 0;}