九度oj-1090

题目描述：

给你一串路径，譬如：
a\b\c
a\d\e
b\cst
d\
你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右缩一格，就像这样：
a
  b
    c
  d 
    e
b
  cst
d
同一级的需要按字母顺序排列，不能乱。

输入：

每个测试案例第一行为一个正整数n（n<=10）表示有n个路径，当n为0时，测试结束，接下来有n行，每行有一个字串表示一个路径，长度小于50。

输出：

输出目录结构，每一个测试样例的输出紧跟一个空行。

样例输入：

4
a\b\c
a\d\e
b\cst
d\
0

样例输出：

a
  b
    c
  d
    e
b
  cst
d

代码：

#include <iostream>  
#include <string>  
using namespace std;  

typedef struct node{   
    string name;   
    struct node * first_child;  
    struct node * next_sibling;  
}Node;   

Node* createNode(string name){   
    Node* n = new Node;   
    n->name = name;   
    n->first_child = NULL;  
    n->next_sibling = NULL;  
    return n;  
}   

void build(Node *root, string path){   
    if (path =="") return ;  
    string::size_type idx = path.find("\\");    
    if(idx == string::npos) idx = path.length();   
    string name = path.substr(0,idx); //child name   
    if(idx!=path.length()) idx++;  
    path = path.substr(idx); //left path  
    Node * ch,*pre;  
    bool exist = false;  
    //find right place for child  
    for (ch = root->first_child, pre=root; ch!=NULL; pre=ch,ch=ch->next_sibling ) {   
        if(ch->name == name){   
            exist = true;  
            break;  
        }else if(ch->name > name){   
            break;   
        }       
    }  
    if(exist){   
        build(ch,path);    
    }else{   
        Node* newNode = createNode(name);  
        if(pre == root){   
            pre->first_child = newNode;    
        }else{   
            pre->next_sibling = newNode;   
        }      
        newNode->next_sibling = ch;  
        build(newNode,path);   
    }    
}    

void destroy(Node * root){   
    if(root == NULL) return;    
    destroy(root->first_child);  
    destroy(root->next_sibling);   
    delete root;  
}   

void dfs(Node * root,int addLen){   
    if(root == NULL) return ;    
    for (int i = 0; i < addLen; ++i) cout<<" ";   
    if(root->name !="") cout<<root->name<<endl;   
    if(root->first_child) dfs(root->first_child,(int)root->name.length()+addLen+1);   
    if(root->next_sibling) dfs(root->next_sibling,addLen);    

}    
int main(){   
    //freopen("in/1090.in","r",stdin);   
    //freopen("out/1090.out","w",stdout);   
    int n;   
    string path;  
    while(cin>>n && n!=0){   
        Node * root = createNode("");   
        while(n--){   
            cin>>path;   
            build(root,path);   
        }    
        dfs(root,-1);   
        cout<<endl;  
        destroy(root);  
    }    
}    

作者提醒：

使用二叉树表示多叉树。 在每层找对应的文件名，如果没有就新建。然后继续向下查找（或创建）。