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

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

这里有一个简单的方法，遍历对象列表三次，将树节点放入字典（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

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

Construct hierarchy tree from python flat parent-children dict list

python

arrays

tree

json

hierarchy