在不使用 class/object 的情况下递归创建树层次结构

Question

我在 Python 3 中创建树层次结构时遇到问题。我希望能够在不使用类的情况下执行此操作。

我需要开始的数据不按顺序且格式不正确 ['ID','Parent']:

data=[['E1', 'C1'],['C1', 'P1'],['P1', 'R1'],['E2', 'C2'],['C2', 'P2'],['P2', 'R1'],['C3', 'P2'],['E3', 'C4'],['C4', 'P3'],
  ['P3', 'R2'],['C5', 'P3'],['E4', 'C6'],['C6', 'P4'], ['P4', 'R2'],['E5', 'C7'],['C7', 'P5'],['P5', 'R3'],['E6', 'C9'],['C9', 'P6'],['P6', 'R3'],
  ['C8', 'P6'],['E7', 'C10'],['C10', 'P7'],['P7', 'R4'],['C11', 'P7'],['E8', 'C12'],['C12', 'P8'],['P8', 'R4']]

我想在不使用类的情况下创建 (Tree) 字典变量 ，结果如下：

Tree={'R1':{'P1':{},'P2':{}},'R2':{}} etc

或

Tree={'R1':[{'P1':[],'P2':[]}],'R2':[]} etc

显然 R1 和 R2 比那个多 children 但也许这就是树结构的样子？

Answer 1

您可以简单地遍历每个 child、parent 元组，创建将子元素和父元素的 ID 映射到包含这些元素的子元素的列表的字典。我们一直这样做，直到完成。

roots = set()
mapping = {}
for child,parent in data:
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

现在我们已经完成了，roots 是一组树根的 id：所以对于每个这样的元素，我们知道没有 id 是父元素。对于 roots 中的每个 id，我们可以简单地从 mapping 中获取，这是结构 {'childid':child} 的字典，其中 childid 是 id（这里是 string) 并且 child 又是那种形式的字典。

因此您可以像这样打印它们：

for root in roots:
    print(mapping[root])

所以在你的情况下，tree 是：

tree = { id : mapping[id] for id in roots }

对于您的示例 data，它生成：

>>> tree
{'R1': {'P1': {'C1': {'E1': {}}}, 'P2': {'C2': {'E2': {}}, 'C3': {}}}, 'R2': {'P4': {'C6': {'E4': {}}}, 'P3': {'C5': {}, 'C4': {'E3': {}}}}, 'R3': {'P6': {'C8': {}, 'C9': {'E6': {}}}, 'P5': {'C7': {'E5': {}}}}, 'R4': {'P8': {'C12': {'E8': {}}}, 'P7': {'C11': {}, 'C10': {'E7': {}}}}}

在不使用 class/object 的情况下递归创建树层次结构

Recursively creating a tree hierarchy without using class/object

python

tree

recursion

hierarchy

python-3.x