Реализовать глубину первого обхода дерева со стеком в 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» равен этому идентификатору), используйте стек, чтобы отслеживать их, и увеличивайте уровень каждый раз / сортируйте по алфавиту для всех дочерних элементов узла.

Как бы вы моглиреализовать это создание дерева (узел + потомки) и обход со стеком (при этом отслеживая уровень, чтобы иметь возможность добавлять дефис и сортировку)?

Вы бы напрямую перешли 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 branch

tree = 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
-Manhattan
San Francisco Bay Area
-San Francisco
-South Bay
--San Jose