Как создать класс для хранения иерархичных данных

Question

Есть список. Как эти данные хранить в классе?

input= [
    (None, 'a'),
    (None, 'b'),
    (None, 'c'),
    ('a', 'a1'),
    ('a', 'a2'),
    ('a2', 'a21'),
    ('a2', 'a22'),
    ('b', 'b1'),
    ('b1', 'b11'),
    ('b11', 'b111'),
    ('b', 'b2'),
    ('c', 'c1'),
]

Примерный вид класса такой. Непонятно как задать родительский элемент

class Node(object):
    def __init__(self):
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

Answer 1

Если нужно хранить родительский элемент явно, то нужно еще одно поле:

class Node(object):
    def __init__(self, parent):
        self.parent = parent
        parent.add_child(self) 
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

Answer 2

Добавил в структуру название, родителя, завел специальный узел - корневой элемент

При заполнении элементов использовал словарь, чтобы упростить поиск элементов

Для проверки работы структуры сделал метод Node.print для рекурсивного вывода элемента и всех его детей

class Node:
    def __init__(self, name: str, parent: 'Node' = None):
        self.name = name
        self.parent = parent
        self.children = []

    def add_child(self, obj: 'Node'):
        self.children.append(obj)

    @property
    def parent_name(self) -> str:
        return self.parent.name if self.parent else None

    def __repr__(self) -> str:
        return f'Node(name={self.name!r}, parent={self.parent_name!r}, children_len={len(self.children)})'

    def print(self):
        def _print(node: Node, level=0):
            print('    ' * level + f'{node.name} ({len(node.children)})')
            for child in node.children:
                _print(child, level + 1)

        _print(self)


source = [
    (None, 'a'),
    (None, 'b'),
    (None, 'c'),
    ('a', 'a1'),
    ('a', 'a2'),
    ('a2', 'a21'),
    ('a2', 'a22'),
    ('b', 'b1'),
    ('b1', 'b11'),
    ('b11', 'b111'),
    ('b', 'b2'),
    ('c', 'c1'),
]

name_by_node = dict()
name_by_node[None] = Node('ROOT', None)

for parent, child in source:
    parent_node = name_by_node[parent]
    if child not in name_by_node:
        name_by_node[child] = Node(child, parent_node)

    parent_node.add_child(name_by_node[child])

name_by_node[None].print()

Рекурсивный вывод:

ROOT (3)
    a (2)
        a1 (0)
        a2 (2)
            a21 (0)
            a22 (0)
    b (2)
        b1 (1)
            b11 (1)
                b111 (0)
        b2 (0)
    c (1)
        c1 (0)

UPD.

Для генерации словаря нужно добавить метод:

    def to_dict(self) -> dict:
        def _to_dict(node: Node):
            return {
                'name': node.name,
                'parent': node.parent_name,
                'children': [_to_dict(child) for child in node.children],
            }

        return _to_dict(self)

Вызываем (для удобства показываем в json):

data = name_by_node[None].to_dict()
print(json.dumps(data, indent=4, ensure_ascii=False))

Результат:

{
    "name": "ROOT",
    "parent": null,
    "children": [
        {
            "name": "a",
            "parent": "ROOT",
            "children": [
                {
                    "name": "a1",
                    "parent": "a",
                    "children": []
                },
                {
                    "name": "a2",
                    "parent": "a",
                    "children": [
                        {
                            "name": "a21",
                            "parent": "a2",
                            "children": []
                        },
                        {
                            "name": "a22",
                            "parent": "a2",
                            "children": []
                        }
                    ]
                }
            ]
        },
        {
            "name": "b",
            "parent": "ROOT",
            "children": [
                {
                    "name": "b1",
                    "parent": "b",
                    "children": [
                        {
                            "name": "b11",
                            "parent": "b1",
                            "children": [
                                {
                                    "name": "b111",
                                    "parent": "b11",
                                    "children": []
                                }
                            ]
                        }
                    ]
                },
                {
                    "name": "b2",
                    "parent": "b",
                    "children": []
                }
            ]
        },
        {
            "name": "c",
            "parent": "ROOT",
            "children": [
                {
                    "name": "c1",
                    "parent": "c",
                    "children": []
                }
            ]
        }
    ]
}

БЛОГ НА HUSL

Как создать класс для хранения иерархичных данных

Ответы (2 шт):