Создать дерево из заданного словаря

Question

У меня есть словарь Python, и я хотел бы создать дерево из него.Словарь выглядит примерно так:

dict_={"2":{'parent': "1"},"1":{'parent': None},"3":{'parent': "2"}}

. В данном случае корень - «1»

. Я пытался использовать библиотеку treelib, но проблема возникает при итерации по словарю и созданииузел, его родитель еще не создан.Например, если я хочу создать узел для «2», его родитель («1») еще не создан, поэтому не могу этого сделать.Любая идея?

Answer 1

Вы можете сделать следующее.Сначала преобразуйте структуру данных в отображение parent-children:

from collections import defaultdict

d = defaultdict(list)  # parent: List[children]
for k, v in dict_.items():
    d[v['parent']].append(k)

Затем, начиная с корня

root = d[None][0]

tree = Tree()
tree.create_node(root, root)

Создайте дерево сверху:

agenda, seen = [root], set([root])
while agenda:
    nxt = agenda.pop()
    for child in d[nxt]:
        tree.create_node(child, child, parent=nxt)
        if child not in seen:
            agenda.append(child)
            seen.add(child)

Answer 2

Вы можете сделать следующее, используя treelib:

from treelib import Node, Tree

dict_ = {"2": {'parent': "1"}, "1": {'parent': None}, "3": {'parent': "2"}}

added = set()
tree = Tree()
while dict_:

    for key, value in dict_.items():
        if value['parent'] in added:
            tree.create_node(key, key, parent=value['parent'])
            added.add(key)
            dict_.pop(key)
            break
        elif value['parent'] is None:
            tree.create_node(key, key)
            added.add(key)
            dict_.pop(key)
            break

tree.show()

Выход

1
└── 2
    └── 3

Идея состоит в том, чтобы добавить узел, только если присутствует родительв дереве или родительском None.Когда родителем является None, добавьте его как root.