从python扁平父子字典列表构造层次树 [英] Construct hierarchy tree from python flat parent-children dict list

问题描述

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

I have a dict list with the following structure:

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

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

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

[
"com.company.object.Being" : [
        "com.company.object.kind.StaticBeing": [
            "com.company.object.kind.type.Solid",
            "com.company.object.kind.type.Liquid"
        ],
        "com.company.object.kind.LivingBeing": [
            "com.company.object.kind.type.Animal": [
                "com.company.object.kind.type.subtype.Fish",
                "com.company.object.kind.type.subtype.Mammal": [
                    "com.company.object.kind.type.subtype.family.Canine": [
                        "com.company.object.kind.type.subtype.family.species.Wolf",
                        "com.company.object.kind.type.subtype.family.species.Hyena"
                    ],
                    "com.company.object.kind.type.subtype.family.Feline": [
                        "com.company.object.kind.type.subtype.family.species.Lion",
                        "com.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.

这篇关于从python扁平父子字典列表构造层次树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！