题目：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
TNODE *queue[100];/*队列，用于输入*/
TNODE *stack[100];/*栈，用于输出*/
int head, tail; /*队列的全局指针*/
int top; /*栈的全局指针*/
TNODE* InputTree();
void ParseLine(char*, int);
void AddChildNodes(char*, int);
void OutputTree(TNODE *head);
/*读入并组装为一棵树，返回根结点指针*/
TNODE* InputTree()
{
int size, depth=0;/*队列的指针*/
char buf[11], line[1024];
TNODE *node=NULL, *root=NULL;
/*是否读到了文件尾部，如果读到空字符串也返回null*/
if(scanf("%s %d", buf, &size)==EOF || size<0)
return NULL;
head=tail=0;
/*申请首个节点空间，赋值，入列*/
root=(TNODE*)malloc(sizeof(TNODE));
memset(root, 0, sizeof(TNODE));
root->size=size;
strcpy(root->text, buf);
queue[tail++]=root; /*首个节点入队列*/
/*循环读入后续的每一行*/
while(head!=tail)
{
gets(line);
ParseLine(line, depth++); /*解析这一行！实际就是装配树的过程！*/
/*如果这一行中没有星号，说明树已经输入完毕！*/
}
return root;
}
/*解析当前输入的一行，depth为节点所在深度*/
void ParseLine(char *line, int depth)
{
char *begin, *s;
int flag=0;
begin=s=line;
while(*s)
{
switch(*s)
{
case '(':
begin=s+1;
break;
case ')':
*s='\0';
AddChildNodes(begin, depth);
break;
}
s++;
}
}
/*添加子节点, depth为节点所在深度*/
void AddChildNodes(char *str, int depth)
{
TNODE *parent, *node, *temp;
char *token;
int i=0;/*子节点索引*/
token=strtok(str, " ");
/*出列一个节点！*/
parent=queue[head++];
while(token!=NULL)
{
node=(TNODE*)malloc(sizeof(TNODE));
memset(node, 0 ,sizeof(TNODE));
node->depth=depth;
strcpy(node->text, token);
/*看该节点是否应该入列，如果是文件夹，则入列！*/
if(token[0]=='*')
queue[tail++]=node;
/*读入size*/
token=strtok(NULL, " ");
node->size=atoi(token);
/*添加该子节点！*/
parent->child[i++]=node;
node->parent=parent;
/*累加父节点的size！*/
temp=parent;
while(temp!=NULL)
{
temp->size+=node->size;
temp=temp->parent;
}
token=strtok(NULL, " ");
}
}
注意在上面的代码中，我们在AddChildNodes函数的最后面对节点的size进行向根结点方向的追踪累加，这样树组装完毕后，每个节点的size就是最终要输出的值。
当树读取进来并且组装以后，我们只需要对这个树进行前序遍历，依次打印节点即可，这部分的内容比较简单。但显然在输出中存在很关键的打印技巧，即如何准确打印出树的形状，每一个节点前面的前导字符串是关键！每一行由下面的格式组成：
[前缀字符串] |_ [节点名称] [size]
这里唯一有难度和技巧性的是前缀字符串的确定，每一深度的缩进由8个空格组成，但有时第一个空格实际上是竖线。那么竖线是否出现的规律是什么呢？仔细观察我们可以发现，当该节点的父节点是祖父节点的最后一个子节点（即老幺）时，父节点下方将不包含竖线。否则这8个空格中的第一个被替换为'|'。这样我们就不难写出下面的代码，提供一个缓冲区，然后我们把它设置为正确的前缀字符串：
Code_设置前缀字符串
/*很关键的一个函数，设置某个节点的前导部分*/
void SetPrefix(TNODE *node, char *buffer)
{
int i, depth=node->depth;
TNODE *temp, *parent=NULL;
if(node->depth>0)
memset(buffer, ' ', node->depth * 8);
buffer[node->depth * 8]='\0'; /*结尾*/
/*从下向上去判断！注意depth=0时无需要判断，因为根结点是“独子”，注定是“老幺”*/
temp=node->parent;
while(temp!=NULL && (temp->depth > 0))
{
parent=temp->parent;
/*从父节点的子节点集合中最后向前找，如果不是最后一个节点，则把空格改为竖线*/
for(i=9;i>=0;i--)
{
/*如果temp不是父节点的最后一个子节点（老幺）*/
if(parent->child[i]!=NULL && parent->child[i]!=temp)
{
buffer[temp->depth*8]='|';
break;
}
if(parent->child[i]==temp) /*是最后一个节点*/
break;
}
temp=parent;
}
}
最后我们就可以用常规的栈前序遍历输出结果：
Code_用栈辅助来前序遍历输出
/*借助栈的辅助，前序输出，并输出后释放相应节点！*/
void OutputTree(TNODE *head)
{
TNODE *node;
char prefix[80];/*该节点的前导字符串*/
int i;
if(head==NULL)
return;
top=0; /*栈顶指针*/
/*根结点入栈*/
stack[top++]=head;
/*当栈不为空时*/
while(top>0)
{
node=stack[--top]; /*pop a node*/
/*在这里我们设置节点的前导！非常关键的一个地方！！！*/
SetPrefix(node, prefix);
/*打印该节点*/
printf("%s|_%s[%d]\n", prefix, node->text, node->size);
/*node的子节点从右到左入栈！*/
for(i=9;i>=0;i--)
{
if(node->child[i]!=NULL)
stack[top++]=node->child[i];
}
}
}
同时我们在输出完一棵树以后，在读取下一颗树之前，应当把当前的树说申请的内存还给系统。由于刚刚使用栈输出过这棵树，因此这棵树的所有节点实际上都位于辅助栈内。因此我们只需要把栈里所有节点释放即可：
Code_释放树占用的内存
/*此时应该是刚刚输出完毕树，只要清空堆栈里的所有节点即可*/
void DeleteTree()
{
int i=0;
for(i=0;i<100;i++)
{
if(stack[i]==NULL)
break;
free(stack[i]);
stack[i]=NULL;
}
}
/*入口点*/
int main()
{
TNODE *tree;
while((tree=InputTree())!=NULL)
{
OutputTree(tree);
DeleteTree();/*释放栈中的所有节点！*/
}
return 0;
}
最后，我们再关注一下需要注意的事项：
（1）我们在输出所有节点以后，才统一的一次性释放所有节点。而不是每输出一个节点就当即释放一个节点。这样做的原因是我们需要用节点关系去推导前缀字符串，因此我们没有立即就释放已经遍历过的节点。
（2）我们使用malloc申请了一个节点以后，请注意这样的内存是“原始”的，也就是未经过任何初始化的，因此如果里面包含指针（例如节点的父节点指针，所有子节点指针），则这些指针全部属于“野指针”状态。如果不对这些指针进行初始化，将会导致灾难性后果。所以每次申请到一个节点后我们必须要做的第一步是初始化它：即memset( node, 0, sizeof(TNODE)); 这一条语句将保证节点中所有指针被设置为NULL，切不可忘记！！！
（3）实际上由于输入和输出是完全顺序的操作，因此这里的辅助栈和辅助队列可以合并为一个，它是queue还是stack完全取决于我们如何使用它。但为了清晰起见，我们的代码还是保留为独立的queue和stack空间。
（4）此题看似容易，但实际上包含了相当的技巧性，并不是很容易在短时间内写好，从它较低的AC率（24%）来看说明它也不是一道简单的送分题。我仔细调试和检查了代码，直到全部正确才提交，然后一次性AC了，运行时间和内存占用都和解排行榜上的数据一致。