使用Python从父子列表构建树结构

Question

使用Python，我有一个dictionary对象列表，其中包含彼此之间的父/子关系，我希望将其构建到树中。例如：

{'UI': 'T071', 'NAME': 'Entity', 'PARENT': None, 'CHILDREN': 'Conceptual Entity'}
{'UI': 'T077', 'NAME': 'Conceptual Entity', 'PARENT': 'Entitity', 'CHILDREN': 'Organism Attribute, Finding, Idea or Concept'}
{'UI': 'T032', 'NAME': 'Organism Attribute', 'PARENT': 'Conceptual Entity', 'CHILDREN': 'Clinical Attribute'}
etc.

数据集中总共有4个根节点（用‘父’集为无），这构成了4个独立的树。所以，我打算列一张树的单子。

数据不一定以任何形式排序（因此层次结构中较高的节点不一定在列表中较高）。此外，id（UI）没有特定的顺序（T071在树中不一定比T072高）。它们的名称是唯一的，数据集使用它们的名称而不是id（UI）来显示关系。

我有一个简单的课程：

class node():
    def __init__(self, value):
        self.value = value
        self.children = []

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

我对如何处理这个问题有点困惑。非常感谢你的建议。

Answer 1

我认为最好的办法是两次传球。首先，创建一个将名称链接到节点的字典。然后你可以有效地添加你的项目。

我的代码：

nodes = dict((e["NAME"], node(e)) for e in l)
for e in l:
    if e["PARENT"] is not None:
        nodes[e["PARENT"]].add_children(nodes[e["NAME"])

如果需要根，可以使用上面的If，也可以筛选节点。

roots = [n for n in nodes.values() if d.value["PARENT"] is None]

Answer 2

我曾经用一个dict表示了一个*ix进程树，并为每个父进程pid列出了子进程pid。所以你得到：

dict_[1] = [2, 3, 4]
dict_[2] = [5, 100]
dict_[3] = [6, 200]
dict_[4] = [7, 300]
dict_[6] = [400]

看来效果不错。

您可以选择是希望叶节点与空列表一起存在，还是不显示在树中。我已经在上面展示了它们，它们没有出现在dict级别的树中。

我相信只有当pid（节点）只能出现在树中的一个位置时，这才是合适的。100不能是2和4的孩子。