在 Python 中使用堆栈实现深度优先树遍历

Question

如果给出位置的 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 并执行此过程，还是创建一个单独的结构工具和树然后执行此操作？希望为其中一些不同步骤提供一些代码 - 我知道如何解决它，我只是不清楚确切的实现。

Answer 1

您可以根据给定的数据构建此“树”，如下所示：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 branchtree = find_children(None, locations)print(tree)哪个打印{'San Francisco Bay Area': {'San Francisco': {}, 'South Bay': {'San Jose': {}}}, 'New York': {'Manhattan': {}}}然后，您可以对以下内容进行排序和打印tree：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-ManhattanSan Francisco Bay Area-San Francisco-South Bay--San Jose