Python使用“parent”键从平面dict创建嵌套结构

Question

让我们考虑一下Python 3中的这个示例：

class SimpleObj:
    def __init__(self, own_id: int, parent_id: int):
        self.parent_id = parent_id
        self.own_id = own_id
        self.children_objects = []  # type: List[SimpleObj]

test_dict = {}
test_dict[0] = SimpleObj(own_id=0, parent_id=-1)  # -1 will mean root node
test_dict[1] = SimpleObj(own_id=1, parent_id=0)
test_dict[123] = SimpleObj(own_id=123, parent_id=1)
test_dict[5] = SimpleObj(own_id=5, parent_id=123)

创建递归嵌套结构（例如SimpleObj with own_id=1将其children_objects列表填充一个元素，该元素将是SimpleObj with own_id=123）的最python的方法是什么？ 它闻起来很像二叉树问题，但我真的没有找到一个有效的解决办法，把这种字典变成一个树一样的对象结构

Answer 1

可能您可以创建一个小函数来处理新SimpleObj的创建：

class SimpleObj:
    def __init__(self, own_id: int, parent_id: int):
        self.parent_id = parent_id
        self.own_id = own_id
        self.children_objects = []


def addSimpleObj(struct, own_id, parent_id):
    struct[own_id] = SimpleObj(own_id=own_id, parent_id=parent_id)
    if parent_id != -1:
        try:
            struct[parent_id].children_objects.append(struct[own_id])
        except IndexError:
            print('the parent_id does not exists')

test_dict = {}
addSimpleObj(test_dict, 0, -1)
addSimpleObj(test_dict, 1, 0)
addSimpleObj(test_dict, 123, 1)
addSimpleObj(test_dict, 5, 123)

这只是一个开始，但似乎成功了。您可以修改它来处理，例如，您尝试为已经存在的键重新创建SimpleObj的情况

Answer 2

经过反复研究，我想出了自己的解决办法。有两个主要的问题需要克服-递归和处理节点引用尚未出现的父母。这是我的解决办法。它尝试递归地将对象分配给它们的父对象，如果失败，它将创建一个孤立对象列表。然后，它遍历孤立节点列表，直到所有节点都就位。我在多个配置上进行了测试，它看起来总是可以工作的（只要输入正确，就意味着没有重复或循环引用等）

from __future__ import annotations
from typing import List


class SimpleObj:
    def __init__(self, parent_id: int, own_id: int):
        self.own_id = own_id
        self.parent_id = parent_id
        self.children_objects = []  # type: List[SimpleObj]

    def assign_to_children(self, what_to_assign: SimpleObj):
        if what_to_assign.parent_id == self.own_id:
            self.children_objects.append(what_to_assign)
            return True
        else:
            for child in self.children_objects:
                if child.assign_to_children(what_to_assign=what_to_assign):
                    return True

    def __repr__(self):
        return f"ID: {self.own_id}, PARENT: {self.parent_id}"

test_objects_list = [SimpleObj(own_id=69, parent_id=70),
                     SimpleObj(own_id=59, parent_id=71),
                     SimpleObj(own_id=70, parent_id=71),
                     SimpleObj(own_id=71, parent_id=1),
                     SimpleObj(own_id=1, parent_id=0),
                     SimpleObj(own_id=2, parent_id=1),
                     SimpleObj(own_id=44, parent_id=1),
                     SimpleObj(own_id=6, parent_id=44),
                     SimpleObj(own_id=14, parent_id=10),
                     SimpleObj(own_id=10, parent_id=1)]

def create_tree_from_list_of_obj(list_in: List[SimpleObj]):
    # find root
    root = [obj for obj in list_in if obj.parent_id == 0][0]
    list_in.remove(root)
    print(root)

    orphans = []
    # do the actual work
    for obj in list_in:
        found = root.assign_to_children(obj)
        print(f"Found {obj.own_id}") if found else print(f"Not found {obj.own_id}")
        if not found:
            orphans.append(obj)
            print(f"Adding orphaned node with id {obj.own_id}")

    while orphans:
        print(f"\nTrying to fill in {len(orphans)} orphaned nodes...")
        for orphaned_node in orphans[:]:
            found = root.assign_to_children(orphaned_node)
            if found:
                print(f"Found {orphaned_node.own_id}")
                orphans.remove(orphaned_node)
            else:
                print(f"Not found {orphaned_node.own_id}")
    return root

tree = create_tree_from_list_of_obj(test_objects_list)