從蟒蛇平父子字典列表

Question

構造層次樹在這裏需要一點幫助，有以下結構Python字典清單：

[{ "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" }]

，需要在從中構建一個層次樹以下方式：

[ "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" ] ] ] ] ] ] 包可以是不同的，並有任何類型的深度，它只需要從父子關係構造樹。任何人都面對過這個？我不知道如何實現這一點，任何幫助或反饋表示讚賞。

PS：邏輯可以是任何語言，但我更喜歡Csharp或python本身。

Answer 1

這是一種非複雜的方式，循環遍歷對象列表三次，將樹節點放入字典（treenodes）中，並將根節點放入root_node中。

lst是問題中提供的列表。

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字典可能會更好。 這個過程本來可以在一個循環中實現，但它可能非常複雜。

Answer 2

請注意，您在結果中混合了詞典和列表。 假設你想用鑰匙id和children一本字典，然後遞歸的方式來做到這一點...

def build_tree(elems): 
    elem_with_children = {} 

    def _build_children_sub_tree(parent): 
     cur_dict = { 
      'id': parent, 
      # put whatever attributes here 
     } 
     if parent in elem_with_children.keys(): 
      cur_dict["children"] = [_build_children_sub_tree(cid) for cid in elem_with_children[parent]] 
     return cur_dict 

    for item in elems: 
     cid = item['id'] 
     pid = item['parent'] 
     elem_with_children.setdefault(pid, []).append(cid) 

    res = _build_children_sub_tree("com.company.object.Being") 
    return res