Как создать вложенный список родительских/дочерних объектов с помощью функции?

Я новичок в Python и Django и столкнулся с проблемой, которую не могу решить самостоятельно уже довольно долгое время.

У меня есть база данных, состоящая из множества объектов, и каждый объект имеет одного родителя (кроме первого, "корневого" объекта) и ни одного / одного / нескольких детей. Мне нужно создать функцию, которая принимает некоторый объект и возвращает этот объект и рекурсивно его потомков следующим образом:

arr = ['States',
       ['Kansas', ['Lawrence', 'Topeka', ['Some Topeka Street', ['Some House on Some Topeka Street']]],
        'Illinois', ['Chicago', 'Springfield']]]

Я хочу получить такую структуру данных и использовать ее в фильтре Django unordered list.

Насколько я разбираюсь в алгоритмах, я должен составить функцию, которая каким-то образом должна работать следующим образом:

def make_nested_list(item):
    if not item.children: # basic case
        # do something
    else:
        for child in item.children: # recursive case
            # do something
            make_nested_list(child) # function calls itself
    # maybe do something here
    # and finally return self-nested list
    return result

Все, что я пробую, оказывается беспорядочным. Как я могу это сделать?

Предполагая, что ваши item объекты имеют name атрибуты, вот что вы можете сделать:

def list_nodes(siblings):
    for node in siblings:
        yield node.name
        if node.children:
            yield list(list_nodes(node.children))

Итак, аргументом этой функции является список узлов. Если у вас только один корневой объект, то сначала поместите его в список и передайте его в качестве аргумента:

result = list(list_nodes([root]))

Вот тест, который я выполнил, включающий создание макетных данных:

from collections import namedtuple

Node = namedtuple("Node", "name, children")

root = Node("States", [
    Node("Kansas", [
        Node("Lawrence", []), 
        Node("Topeka", [])
    ]), 
    Node("Illinois", [])
])

print(root)

def list_nodes(siblings):
    for node in siblings:
        yield node.name
        if node.children:
            yield list(list_nodes(node.children))

result = list(list_nodes([root]))

print(result)

Вывод (с некоторым форматированием):

Node(name='States', children=[
    Node(name='Kansas', children=[
        Node(name='Lawrence', children=[]), 
        Node(name='Topeka', children=[])
    ]),
    Node(name='Illinois', children=[])
])

['States', ['Kansas', ['Lawrence', 'Topeka'], 'Illinois']]
Вернуться на верх