立志用最少的代码做最高效的表达
在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。
输入格式:
输入首先给出正整数N（≤10^4），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：
路径和名称中的字符仅包括英文字母（区分大小写）；
符号“\”仅作为路径分隔符出现；
目录以符号“\”结束；
不存在重复的输入项目；
整个输入大小不超过2MB。
输出格式:
假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。
输入样例:
7
b
c
ab\cd
a\bc
ab\d
a\d\a
a\d\z
输出样例:
root
a
d
z
a
bc
ab
cd
d
c
b
算法逻辑：
- 设置一个指针指向pos
- 读入目录：将目录插入到以pos为根的子树，把pos更新为插入的地址
插入规则：
首先判断其是否有儿子节点，如果无，则直接建立节点插入即可。
反之，则在其兄弟链中查找位置（儿子节点的兄弟链）。 - 如果是文件，则插入以后结束即可。
- 先序遍历
#include<iostream>
#include<cstdio>
using namespace std;
struct TreeNode{
string str;
TreeNode* child; //左孩子
TreeNode* sibling; //右兄弟
int priority; //为0表示文件，为1表示目录
};
typedef TreeNode* Position;
typedef Position BinTree;
//建树，也可以说是初始化的过程
Position createNode(string s, int priority) {
Position Node = new TreeNode;
Node->str = s;
Node->child = Node->sibling = NULL;
Node->priority = priority;
return Node;
}
//根据root的位置插入节点
/*
插入节点前要想明白一个点，
如果该文件或目录还没有创建，那么创建的一定是其儿子节点。
如果已经创建完毕了，那么插入的位置一定在该节点的右子树中查找。
如
a/b
c/d
1、从根节点插入a后，根节点左子树为a，a的左子树为b
2、从根节点插入c时，发现其左子树已经被占据，那么就遍历其左子树的右子树
也就是根节点左子树的兄弟节点，直到找到合适的位置。遍历d时，也是同理。如果没有被占据，则直接创建儿子节点。
*/
Position insert(BinTree root, string s, int priority) {
if(root->child == NULL) { //如果没有儿子，那么直接插入就可以了
root->child = createNode(s, priority);
return root->child; //下一次插入从儿子开始
}
//定义儿子节点和父亲节点。
Position tmpNode = root->child, father = root;
//如果有儿子，则循链找插入位置
//若待插入节点优先级更小或优先级一致但字典序更大，则继续循链
//注意：边界条件为!=NULL，也就是到了链末尾
while(tmpNode != NULL && ((priority<tmpNode->priority) || (tmpNode->priority == priority && s>tmpNode->str))) {
father = tmpNode;
tmpNode = tmpNode->sibling;
}
//退出循环的三种情况：
//1、找到了链末尾 2、待插文件已存在 3、找到了应该插入的位置
//情况1
if(tmpNode == NULL) {
Position Node = createNode(s, priority);
Node->sibling = father->sibling; //保存一下它的兄弟节点
father->sibling = Node;
return Node;
}
//情况2
if(tmpNode->priority == priority && s==tmpNode->str)
return tmpNode;
//情况3
else {
Position Node = createNode(s, priority);
if(father->str == root->str) { //如果该点为根节点下的第一个节点
Node->sibling = father->child;
father->child = Node;
}
else {
Node->sibling = father->sibling;
father->sibling = Node;
}
return Node;
}
}
//layer是层数，按层数输出空格
void PreorderTraversal(BinTree BT, int layer) {
int i;
int childlayer, siblinglayer;
if(BT) {
for(i = 0; i < layer; i++) printf(" ");
childlayer = layer+1;
siblinglayer = layer;
cout << BT->str << '\n';
PreorderTraversal(BT->child, childlayer);
PreorderTraversal(BT->sibling, siblinglayer);
}
}
int main() {
int N, i, bgn, end, j;
string str;
Position pos; //说是指针，其实就是节点
BinTree root = createNode("root", 1);
scanf("%d\n", &N);
for(i = 0; i < N; i++) {
getline(cin, str);
pos = root;
bgn = end = 0; //记录文件首字符和最后一个字符的位置
for(j = 0; j < str.length(); j++) {
if(str[j] == '\\') {
end = j;
pos = insert(pos, str.substr(bgn, end-bgn), 1);
bgn = end+1; //每次插入完成后更新起始字符位置
}
}
//读完所有目录后判断字符串中是否还有文件 如果有，读入文件
if(str[bgn] != '\0') {
insert(pos, str.substr(bgn, str.length()-bgn), 0);
}
}
PreorderTraversal(root, 0); //前序遍历输出
return 0;
}