在Python中从父/子列表构建树

Question

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

{'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个根节点(“PARENT”设置为“None”)，这就形成了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]

它似乎工作得很好。

它是可选的，是希望叶节点以空列表存在，还是不出现在树中。我已经在上面展示了它们，它们不会出现在字典级别的树中。

我认为只有当pid (节点)只能出现在树中的一个位置时，这才是合适的。例如，100不能是2和4的孩子。

Answer 3

代码可以深入到字典树中的5个级别。当到达某个对象时，它会检查该对象是否为numpy。如果是，它会打印出它的形状。如果不是，则写入对象的类型。通过选择“级别”，它可以确定树应该深入到多深。目前的实现深入到了5个级别。

def tree_view_dict(d, level=999):
    for key in d.keys():
        print('|')
        print(key, end = '')
        if isinstance(d[key], dict) and level > 1:
            print()
            for key2 in d[key].keys():
                print('|__', key2, end = '')
                if isinstance(d[key][key2], dict) and level > 2:
                    print()
                    for key3 in d[key][key2]:
                        print('   |__', key3, end = '')
                        if isinstance(d[key][key2][key3], dict) and level > 3:
                            print()
                            for key4 in d[key][key2][key3]:
                                print('     |__', key4, end = '')
                                if isinstance(d[key][key2][key3][key4], dict) and level > 4:
                                    print()
                                    for key5 in d[key][key2][key3][key4]:
                                        print('       |__', key5, end = '')
                                else:
                                    print(': ', d[key][key2][key3][key4].shape if type(d[key][key2][key3][key4]).__module__ == 'numpy' else type(d[key][key2][key3][key4]))
                        else:
                            print(': ', d[key][key2][key3].shape if type(d[key][key2][key3]).__module__ == 'numpy' else type(d[key][key2][key3]))
                else:
                    print(': ', d[key][key2].shape if type(d[key][key2]).__module__ == 'numpy' else type(d[key][key2]))
        else:
            print(': ', d[key].shape if type(d[key]).__module__ == 'numpy' else type(d[key]))
    pass

d = {'UI': 'T032', 'NAME': 'Organism Attribute', 'PARENT': 'Conceptual Entity', 'CHILDREN': {'CHILDREN_array': np.array([[1,2], [3,4]]),'CHILDREN_name': 'name'}}
tree_view_dict(d, level=5)

结果是，

|
UI:  <class 'str'>
|
NAME:  <class 'str'>
|
PARENT:  <class 'str'>
|
CHILDREN
|__ CHILDREN_array:  (2, 2)
|__ CHILDREN_name:  <class 'str'>```