01760: Disk Tree

前缀树（Trie），http://cs101.openjudge.cn/practice/01760/

Hacker Bill has accidentally lost all the information from his workstation's hard drive and he has no backup copies of its contents. He does not regret for the loss of the files themselves, but for the very nice and convenient directory structure that he had created and cherished during years of work. Fortunately, Bill has several copies of directory listings from his hard drive. Using those listings he was able to recover full paths (like "WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86") for some directories. He put all of them in a file by writing each path he has found on a separate line. Your task is to write a program that will help Bill to restore his state of the art directory structure by providing nicely formatted directory tree.

输入

The first line of the input file contains single integer number N (1 <= N <= 500) that denotes a total number of distinct directory paths. Then N lines with directory paths follow. Each directory path occupies a single line and does not contain any spaces, including leading or trailing ones. No path exceeds 80 characters. Each path is listed once and consists of a number of directory names separated by a back slash \.

Each directory name consists of 1 to 8 uppercase letters, numbers, or the special characters from the following list: exclamation mark, number sign, dollar sign, percent sign, ampersand, apostrophe, opening and closing parenthesis, hyphen sign, commercial at, circumflex accent, underscore, grave accent, opening and closing curly bracket, and tilde ("!#$%&'()-@^_`{}~").

输出

Write to the output file the formatted directory tree. Each directory name shall be listed on its own line preceded by a number of spaces that indicate its depth in the directory hierarchy. The subdirectories shall be listed in lexicographic order immediately after their parent directories preceded by one more space than their parent directory. Top level directories shall have no spaces printed before their names and shall be listed in lexicographic order. See sample below for clarification of the output format.

样例输入

7
WINNT\SYSTEM32\CONFIG
GAMES
WINNT\DRIVERS
HOME
WIN\SOFT
GAMES\DRIVERS
WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86

样例输出

GAMES
 DRIVERS
HOME
WIN
 SOFT
WINNT
 DRIVERS
 SYSTEM32
  CERTSRV
   CERTCO~1
    X86
  CONFIG

来源

Northeastern Europe 2000

这道题本质上是 前缀树（Trie） 的应用场景！我们可以使用 Trie 结构 来存储和组织目录路径，并通过 递归遍历 来打印出格式化的目录树。

为什么适合使用前缀树（Trie）？

前缀共享：不同路径可能有公共前缀，使用 Trie 可以高效存储和查询这些前缀，而无需重复存储相同的部分。
层次结构：Trie 本身是一个 树结构，天然适合表示 文件系统 这种 层次化目录结构。
字典序排序：Trie 的子节点本质上是字典，可以按键排序，方便按照要求字典序输出。

python

from collections import defaultdict
import sys

class TrieNode:
    """Trie 结点类"""
    def __init__(self):
        self.children = defaultdict(TrieNode)  # 存储子目录
        self.is_end = False  # 该标志在本题中可省略

class Trie:
    """Trie 前缀树"""
    def __init__(self):
        self.root = TrieNode()

    def insert(self, path: str):
        """插入目录路径"""
        node = self.root
        for folder in path.split("\\"):  # 以 "\" 分割路径
            node = node.children[folder]  # 如果不存在则自动创建

    def print_tree(self, node=None, depth=0):
        """递归打印目录树"""
        if node is None:
            node = self.root
        for folder in sorted(node.children):  # 按字典序排序
            print(" " * depth + folder)  # 根据深度打印
            self.print_tree(node.children[folder], depth + 1)  # 递归打印子目录

def main():
    # 读取输入
    n = int(sys.stdin.readline().strip())
    trie = Trie()

    for _ in range(n):
        path = sys.stdin.readline().strip()
        trie.insert(path)

    # 输出目录树
    trie.print_tree()

if __name__ == "__main__":
    main()

Trie 结构
insert(path)：将路径拆分成目录层级，并插入 Trie。
print_tree(node, depth)：递归遍历 Trie，并 按字典序 打印，使用 深度控制缩进。
时间复杂度分析
插入路径：每个路径最多 80 个字符，总体复杂度 O(N * M)（M 为路径最大深度）。
打印 Trie：遍历整个树，O(N log N)（因排序）。
整体复杂度：O(N log N)，适用于 N ≤ 500。

python

# 23n2300011031
class Node:
    def __init__(self):
        self.children={}
class Trie:
    def __init__(self):
        self.root=Node()
    def insert(self,w):
        cur=self.root
        for u in w.split('\\'):
            if u not in cur.children:
               cur.children[u]=Node()
            cur=cur.children[u]
    def dfs(self,a,layer):
        for c in sorted(a.children):
            print(' '*layer+c)
            self.dfs(a.children[c], layer+1)
s=Trie()
for _ in range(int(input())):
    x=input()
    s.insert(x)
s.dfs(s.root, 0)

python

# 23n2300011072(X)
class Node:
    def __init__(self,name):
        self.name=name
        self.children={}
    def insert(self,path):
        if len(path)==0:
            return
        head,*tail=path
        if head not in self.children:
            self.children[head]=Node(head)
        self.children[head].insert(tail)
    def print_tree(self,depth=0):
        for name in sorted(self.children.keys()):
            print(' '*depth+name)
            self.children[name].print_tree(depth+1)
def build_tree(paths):
    root=Node('')
    for path in paths:
        path=path.split('\\')
        root.insert(path)
    return root
paths=[input() for _ in range(int(input()))]
tree=build_tree(paths)
tree.print_tree()

python

#23n2300017735(夏天明BrightSummer)
def printDir(d, h):
    if not d:
        return
    else:
        for sub in sorted(d.keys()):
            print(' '*h + sub)
            printDir(d[sub], h+1)

n = int(input())
computer = {}
for o in range(n):
    path = input().split('\\')
    curr = computer
    for p in path:
        if p not in curr:
            curr[p] = {}
        curr = curr[p]
printDir(computer, 0)

01760: Disk Tree ​

01760: Disk Tree