从python扁平父子字典列表构造层次树

本文介绍了从python扁平父子字典列表构造层次树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个具有以下结构的字典列表:

I have a dict list with the following structure:

[{ "parent": "company.object.kind.type.subtype.family.Feline", "class": "company.object.kind.type.subtype.family.species.Cat" }, { "parent": "company.object.kind.type.subtype.Mammal", "class": "company.object.kind.type.subtype.family.Feline" }, { "parent": "company.object.Being", "class": "company.object.kind.LivingBeing" }, { "parent": "company.object.kind.type.subtype.family.Canine", "class": "company.object.kind.type.subtype.family.species.Wolf" }, { "parent": "company.object.kind.type.subtype.Mammal", "class": "company.object.kind.type.subtype.family.Canine" }, { "parent": "company.object.kind.type.Animal", "class": "company.object.kind.type.subtype.Mammal" }, { "parent": "company.object.kind.LivingBeing", "class": "company.object.kind.type.Animal" }, { "parent": "company.object.kind.type.Animal", "class": "company.object.kind.type.subtype.Fish" }, { "parent": "company.object.kind.StaticBeing", "class": "company.object.kind.type.Solid" }, { "parent": "company.object.Being", "class": "company.object.kind.StaticBeing" }, { "parent": "company.object.kind.type.subtype.family.Feline", "class": "company.object.kind.type.subtype.family.species.Lion" }, { "parent": "company.object.kind.type.subtype.family.Canine", "class": "company.object.kind.type.subtype.family.species.Hyena" }, { "parent": "company.object.kind.StaticBeing", "class": "company.object.kind.type.Liquid" }]

并且需要通过以下方式从中构造一个层次树:

And need to construct a hierarchy tree from it in the following way:

[ "company.object.Being" : [ "company.object.kind.StaticBeing": [ "company.object.kind.type.Solid", "company.object.kind.type.Liquid" ], "company.object.kind.LivingBeing": [ "company.object.kind.type.Animal": [ "company.object.kind.type.subtype.Fish", "company.object.kind.type.subtype.Mammal": [ "company.object.kind.type.subtype.family.Canine": [ "company.object.kind.type.subtype.family.species.Wolf", "company.object.kind.type.subtype.family.species.Hyena" ], "company.object.kind.type.subtype.family.Feline": [ "company.object.kind.type.subtype.family.species.Lion", "company.object.kind.type.subtype.family.species.Cat" ] ] ] ] ] ]

这些包可以不同，并且具有任何深度类型，只需要从父子关系构建树即可.

The packages can be different and have any type of depth, it just only needs to construct the tree from the parent-child relationships.

推荐答案

这是一种不复杂的方法，它遍历对象列表三次，将树节点放入字典(treenodes)中，然后将根节点放入树中root_node中的节点.

Here is a non-sophisticated way of doing this, looping through the list of objects three times, putting the tree nodes in a dictionary (treenodes) and the root node in root_node.

第一个是问题中提供的列表.

lst is the list provided in the question.

def display_node(node, indent=0): print ('.'*indent, node['class']) indent += 3 for child in node['children']: display_node(child, indent) # Create list of classes classes = [] for item in lst: name = item['class'] if name not in classes: classes.append(name) treenodes = {} root_node = None for item in lst: # Create tree nodes item['children'] = [] name = item['class'] treenodes[name] = item parent = item['parent'] if parent not in classes: # parent is root node, create if parent not in treenodes: node = {} node['parent'] = None node['children'] = [] node['class'] = parent root_node = node treenodes[parent] = node # Connect parents and children for item in lst: # Create tree nodes parent = item['parent'] parent_node = treenodes[parent] parent_node['children'].append(item) display_node(root_node)

最好将节点创建为对象并省去treenodes字典. 该过程本可以在一个循环中完成，但可能非常复杂.

It might be better to create the nodes as objects and dispense with the treenodes dictionary. The process could have been achieved in one loop, but it might have been very complex.