gpt4 book ai didi

python - Python中利用栈实现深度优先树遍历

转载 作者:行者123 更新时间:2023-12-01 01:21:52 28 4
gpt4 key购买 nike

如果给定一个 JSON 位置列表,例如:

locations = [
{"id": 1, "name": "San Francisco Bay Area", "parent_id": None},
{“id": 2, "name": "San Jose", "parent_id": 3},
{"id": 3, "name": "South Bay", "parent_id": 1},
{"id": 4, "name": "San Francisco", "parent_id": 1},
{"id": 5, "name": "Manhattan", "parent_id": 6},
{"id": 6, "name": "New York", "parent_id": None}
]

我希望能够生成位置列表,其中子位置分组在其父位置下,并按字母顺序排列,还用连字符缩进子位置。每个深度级别应按字母顺序排序,并且最多可以有 5 个深度级别。所以上面的输出将是:

New York
-Manhattan
San Francisco Bay Area
-San Francisco
-South Bay
--San Jose

似乎遍历这些位置是有意义的,每当“parent_id”为 None 时,我们就知道这是树的根,因此执行深度优先遍历。找到它的子节点(只要“parent_id”等于此 id),使用堆栈来跟踪它们并每次增加级别/按字母顺序对节点的所有子节点进行排序。

如何实现树(节点+子节点)的创建和堆栈遍历(同时跟踪级别 - 以便能够添加连字符 - 和排序)?

您会直接遍历 JSON 并执行此过程还是创建一个单独的结构实现和树然后执行此过程?希望能提供一些这些不同步骤的代码 - 我知道如何解决它,我只是不清楚确切的实现。

最佳答案

您可以根据给定的数据构建此“树”,如下所示:

locations = [
{"id": 1, "name": "San Francisco Bay Area", "parent_id": None},
{"id": 2, "name": "San Jose", "parent_id": 3},
{"id": 3, "name": "South Bay", "parent_id": 1},
{"id": 4, "name": "San Francisco", "parent_id": 1},
{"id": 5, "name": "Manhattan", "parent_id": 6},
{"id": 6, "name": "New York", "parent_id": None}
]

def find_children(parent, locations):
branch = {}
for location in locations:
if location["parent_id"] == parent:
children = find_children(location["id"], locations)
branch[location["name"]] = children
return branch

tree = find_children(None, locations)
print(tree)

哪个打印

{'San Francisco Bay Area': {'San Francisco': {}, 'South Bay': {'San Jose': {}}}, 'New York': {'Manhattan': {}}}

然后您可以对的内容进行排序和打印:

def print_tree(tree, level=0):
branches = sorted(list(tree.keys()))
for branch in branches:
print("-" * level + branch)
print_tree(tree[branch], level + 1)

print_tree(tree)

哪个打印

New York
-Manhattan
San Francisco Bay Area
-San Francisco
-South Bay
--San Jose

关于python - Python中利用栈实现深度优先树遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53744263/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com