python - 从带有子项的字典数组构建嵌套的树状字典

Question

我有一组从 Web API 检索到的字典。每个字典都有一个 name、description、“parent”和 children 键。 children 键有一个字典数组作为它的值。为了清楚起见，这里有一个虚拟示例:

[
  {'name': 'top_parent', 'description': None, 'parent': None,
   'children': [{'name': 'child_one'},
                {'name': 'child_two'}]},
  {'name': 'child_one', 'description': None, 'parent': 'top_parent',
   'children': []},
  {'name': 'child_two', 'description': None, 'parent': 'top_parent',
   'children': [{'name': 'grand_child'}]},
  {'name': 'grand_child', 'description': None, 'parent': 'child_two',
   'children': []}
]

数组中的每一项。一个项可能是最顶层的父项，因此不存在于任何 children 数组中。一个项目可以既是 child 又是 parent 。或者一个项目只能是一个 child (没有自己的 child )。

所以，在树结构中，你会有这样的东西:

top_parent
  child_one
  child_two
    grand_child

在这个设计和简化的示例中，top_parent 是父对象而不是子对象； child_one 是 child 但不是 parent ； child_two 是 parent 和 child ； grand_child 是一个 child ，但不是 parent 。这涵盖了所有可能的状态。

我想要的是能够遍历字典数组 1 次并生成一个嵌套的字典来正确表示树结构(但是，它 1 次是不可能的，这是最有效的方法)。所以，在这个例子中，我会得到一个看起来像这样的字典:

{
  'top_parent': {
    'child_one': {},
    'child_two': {
      'grand_child': {}
    }
  }    
}

严格来说，没有 child 的项目不一定不是键，但这是更可取的。

Answer 1

第四次编辑，显示了三个版本，稍微清理了一下。第一个版本自上而下工作并根据您的要求返回 None，但实际上循环遍历顶级数组 3 次。下一个版本只循环一次，但返回空字典而不是 None。

最终版本自下而上，非常干净。它可以用一个循环返回空的字典，或者用额外的循环返回 None :

from collections import defaultdict

my_array = [
  {'name': 'top_parent', 'description': None, 'parent': None,
   'children': [{'name': 'child_one'},
                {'name': 'child_two'}]},
  {'name': 'child_one', 'description': None, 'parent': 'top_parent',
   'children': []},
  {'name': 'child_two', 'description': None, 'parent': 'top_parent',
   'children': [{'name': 'grand_child'}]},
  {'name': 'grand_child', 'description': None, 'parent': 'child_two',
   'children': []}
]

def build_nest_None(my_array):
    childmap = [(d['name'], set(x['name'] for x in d['children']) or None)
                for d in my_array]
    all_dicts = dict((name, kids and {}) for (name, kids) in childmap)
    results = all_dicts.copy()
    for (name, kids) in ((x, y) for x, y in childmap if y is not None):
        all_dicts[name].update((kid, results.pop(kid)) for kid in kids)
    return results

def build_nest_empty(my_array):
    all_children = set()
    all_dicts = defaultdict(dict)
    for d in my_array:
        children = set(x['name'] for x in d['children'])
        all_dicts[d['name']].update((x, all_dicts[x]) for x in children)
        all_children.update(children)
    top_name, = set(all_dicts) - all_children
    return {top_name: all_dicts[top_name]}


def build_bottom_up(my_array, use_None=False):
    all_dicts = defaultdict(dict)
    for d in my_array:
        name = d['name']
        all_dicts[d['parent']][name] = all_dicts[name]

    if use_None:
        for d in all_dicts.values():
            for x, y in d.items():
                if not y:
                    d[x] = None

    return all_dicts[None]

print(build_nest_None(my_array))
print(build_nest_empty(my_array))
print(build_bottom_up(my_array, True))
print(build_bottom_up(my_array))

结果:

{'top_parent': {'child_one': None, 'child_two': {'grand_child': None}}}
{'top_parent': {'child_one': {}, 'child_two': {'grand_child': {}}}}
{'top_parent': {'child_one': None, 'child_two': {'grand_child': None}}}
{'top_parent': {'child_one': {}, 'child_two': {'grand_child': {}}}}