题目：1635 Directory Listing（列出目录）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=635
看描述好像是chenyue姐姐出的题目。这道题的大意是，给出一个UNIX文件系统的树，以及树节点的自身size，按要求列出它们，保持适当的缩进，并统计每个节点的总的size。输入的第一行代表根结点，每一个节点由name size或者*name size的形式组成（如果包含*表示这是一个文件夹，它包含的子节点将在下一行中列出，并用圆括号包含，size是一个表示节点自身属性的正整数）。在输出节点时，需要输出该节点自身size和所有子节点size的和。
深度为d的节点前面应该有8d的前导（由空格或竖线组成）；
示范输入：
*/usr 1
(*mark 1 *alex 1)
(hw.c 3 *course 1) (hw.c 5)
(aa.txt 12)
示范输出：
|_*/usr[24]
|_*mark[17]
| |_hw.c[3]
| |_*course[13]
| |_aa.txt[12]
|_*alex[6]
|_hw.c[5]
---------------------------------------------------------------------------------------
题目属于按固定格式输出的题目，但本质上是属于对“树”这种数据结构的考察。不难看出，在读取输入时，输入方式实际上是一种类似树的“按层次遍历”，即按照节点深度从小到大的顺序给出每一层次的节点，第k行即代表了该深度（depth=k）的所有节点。同时，如果节点不包含*，表示是叶子节点，如果包含*，则属于“文件夹”，因此一定会有下一行。如果某一行不包含任何*，则一棵树输入完毕。
而对于输出，容易看出，输出实际上是对树的前序遍历。
在我的此前的一篇博客中，已经详细讲解过如何通过栈来前序遍历树，以及如何通过队列来层次遍历树，因此这里不再详细介绍了。输出的时候完全是前序遍历，无须多做解释。唯一有点特别的是读取输入的过程就是组装这颗树的过程，组装过程中我们先把根结点（一定包含*）入列，然后依次读取下一行，下一行中假设包含n组子节点（即含有n组圆括号），则针对每一组子节点，从队列中出列一个节点作为这些子节点的父节点即可。直到队列为空，一棵树的读取和组装完毕。
这里我们还要注意的第一个细节问题是，在组装过程中，我们还要把该节点的最终size统计出来。因此我们给每个树节点增加了一个父节点指针，这样每挂接一个子节点，从该节点向根结点追溯，对所有父辈节点累加该size。此外我们还需要一个属性记录该节点的所在深度，这个属性在后面的输出时被利用。因此，我们把节点定义如下：
typedef struct tnode
{
char text[11];/*节点名称*/
int depth; /*该节点所在层次*/
int size; /*该节点的当前值，最终值=自身值+所有子节点值*/
struct tnode *child[10]; /*根结点*/
struct tnode *parent; /*父节点，用于向根结点累加size*/
} TNODE;
下面我们即可给出读取并组装树的代码。值得注意的是，我们每次读取一行，而该行中包含的子节点组的个数n是未知的，因此我们需要对读取进来的这一行通过ParseLine函数进行解析，即根据'('和')'字符，把圆括号内部的文本提取出来，再传递给AddChildNodes函数进行处理。
Code_InputTree
注意在上面的代码中，我们在AddChildNodes函数的最后面对节点的size进行向根结点方向的追踪累加，这样树组装完毕后，每个节点的size就是最终要输出的值。
当树读取进来并且组装以后，我们只需要对这个树进行前序遍历，依次打印节点即可，这部分的内容比较简单。但显然在输出中存在很关键的打印技巧，即如何准确打印出树的形状，每一个节点前面的前导字符串是关键！每一行由下面的格式组成：
[前缀字符串] |_ [节点名称] [size]
这里唯一有难度和技巧性的是前缀字符串的确定，每一深度的缩进由8个空格组成，但有时第一个空格实际上是竖线。那么竖线是否出现的规律是什么呢？仔细观察我们可以发现，当该节点的父节点是祖父节点的最后一个子节点（即老幺）时，父节点下方将不包含竖线。否则这8个空格中的第一个被替换为'|'。这样我们就不难写出下面的代码，提供一个缓冲区，然后我们把它设置为正确的前缀字符串：
Code_设置前缀字符串
最后我们就可以用常规的栈前序遍历输出结果：
Code_用栈辅助来前序遍历输出
同时我们在输出完一棵树以后，在读取下一颗树之前，应当把当前的树说申请的内存还给系统。由于刚刚使用栈输出过这棵树，因此这棵树的所有节点实际上都位于辅助栈内。因此我们只需要把栈里所有节点释放即可：
Code_释放树占用的内存
最后，我们再关注一下需要注意的事项：
（1）我们在输出所有节点以后，才统一的一次性释放所有节点。而不是每输出一个节点就当即释放一个节点。这样做的原因是我们需要用节点关系去推导前缀字符串，因此我们没有立即就释放已经遍历过的节点。
（2）我们使用malloc申请了一个节点以后，请注意这样的内存是“原始”的，也就是未经过任何初始化的，因此如果里面包含指针（例如节点的父节点指针，所有子节点指针），则这些指针全部属于“野指针”状态。如果不对这些指针进行初始化，将会导致灾难性后果。所以每次申请到一个节点后我们必须要做的第一步是初始化它：即memset( node, 0, sizeof(TNODE)); 这一条语句将保证节点中所有指针被设置为NULL，切不可忘记！！！
（3）实际上由于输入和输出是完全顺序的操作，因此这里的辅助栈和辅助队列可以合并为一个，它是queue还是stack完全取决于我们如何使用它。但为了清晰起见，我们的代码还是保留为独立的queue和stack空间。
（4）此题看似容易，但实际上包含了相当的技巧性，并不是很容易在短时间内写好，从它较低的AC率（24%）来看说明它也不是一道简单的送分题。我仔细调试和检查了代码，直到全部正确才提交，然后一次性AC了，运行时间和内存占用都和解排行榜上的数据一致。
