路径打印

[编程题]路径打印

热度指数：19843 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给你一串路径，譬如：

a\b\c

a\d\e

b\cst

你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录的首字符向右缩两个空格，就像这样：

cst

注：同一级的需要按字母顺序排列，不能乱。

输入描述:

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

输出描述:

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

示例1

输入

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

输出

a
  b
    c
  d
    e
b
  cst
d

算法知识视频讲解

Python3

chong_0428

class TreeNode:
    def __init__(self):
        self.children = {}  # 存储子目录

def insert_path(root, path):
    # 按'\'分割路径
    dirs = path.strip('\\').split('\\')
    current = root
    
    # 将路径插入到树中
    for d in dirs:
        if d:  # 忽略空目录名
            if d not in current.children:
                current.children[d] = TreeNode()
            current = current.children[d]

def print_tree(node, prefix="", is_root=True):
    # 获取并排序子目录
    dirs = sorted(node.children.keys())
    
    # 打印每个子目录
    for d in dirs:
        print(f"{prefix}{d}")
        # 递归打印子目录，增加缩进
        print_tree(node.children[d], prefix + "  ", False)

def main():
    while True:
        n = int(input())
        if n == 0:
            break
            
        # 创建根节点
        root = TreeNode()
        
        # 读取并处理所有路径
        for _ in range(n):
            path = input().strip()
            insert_path(root, path)
        
        # 打印目录树
        print_tree(root)
        print()  # 每个测试用例后打印空行

if __name__ == "__main__":
    main()

发表于 2025-02-20 21:11:15 回复(0)

Python3

爱吃鱼的小饼干在摸鱼

字典树

class PrefixTree:
    class Node:
        def __init__(self):
            self.nexts = {}

    def __init__(self):
        self.root = self.Node()

    def add(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur.nexts:
                cur.nexts[letter] = self.Node()
            cur = cur.nexts[letter]

    def print(self, cur, blockTimes):
        for letter in sorted(cur.nexts.keys()):
            print(blockTimes * ' ' + letter)
            self.print(cur.nexts[letter], blockTimes + 2)


while 1:
    number = int(input(""))
    if number <= 0:
        break
    prefixTree = PrefixTree()
    while number > 0:
        s = [i for i in input("").split('\\') if i.strip()]
        prefixTree.add(s)
        number -= 1

    prefixTree.print(prefixTree.root, 0)
    print()

发表于 2022-10-18 14:02:04 回复(0)