从蟒蛇平父子字典列表构造层次树

Question

我有以下结构的字典清单：

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

该软件包可以不同，并且有任何类型的深度，它仅仅只需要从父子关系构建树。

Answer 1

这里是这样，通过对象的列表三次循环，把树节点在字典（树节点）和root_node根节点的非成熟的方式。

地表温度的问题提供的列表。

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)

这可能是最好创建节点为对象，并与树节点字典免除。该过程可能在一个循环中已经实现，但它可能是非常复杂的。

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