使用 children 从字典数组构建嵌套的 tree-like 字典

Question

我有一组从网络上检索到的字典 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': []}
]

数组中的每一项。一项可能是 top-most parent，因此不存在于任何 children 数组中。一个项目可以同时是 child 和 parent。或者一个项目只能是 child（没有自己的 children）。

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

top_parent
  child_one
  child_two
    grand_child

在这个人为和简化的示例中，top_parent 是 parent 而不是 child； child_one 是 child 而不是 parent； child_two是一个parent和一个child； grand_child 是 child 而不是 parent。这涵盖了所有可能的状态。

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

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

严格来说，没有children的item不一定不是key，但最好是这样。

Answer 1

您可以保持从名称到节点的惰性映射，然后通过仅处理 parent link 来重建层次结构（我假设数据是正确的，所以如果 A被标记为 B 的 parent iff B 被列在 A 的 children 中）。

nmap = {}
for n in nodes:
    name = n["name"]
    parent = n["parent"]
    try:
        # Was this node built before?
        me = nmap[name]
    except KeyError:
        # No... create it now
        if n["children"]:
            nmap[name] = me = {}
        else:
            me = None
    if parent:
        try:
            nmap[parent][name] = me
        except KeyError:
            # My parent will follow later
            nmap[parent] = {name: me}
    else:
        root = me

输入的 children 属性仅用于知道元素是否应在其 parent 中存储为 None （因为没有 children) 或者它是否应该是一个字典，因为它在重建过程结束时会有 children。将没有 children 的节点存储为空字典会通过避免这种特殊情况的需要来简化代码。

使用collections.defaultdict也可以简化创建新节点的代码

import collections
nmap = collections.defaultdict(dict)
for n in nodes:
    name = n["name"]
    parent = n["parent"]
    me = nmap[name]
    if parent:
        nmap[parent][name] = me
    else:
        root = me

该算法是 O(N) 假设 constant-time 字典访问并且只对输入进行一次传递并且需要 O(N) space 名称->节点映射（ space 原始 nochildren->None 版本的要求是 O(Nc)，其中 Nc 是具有 children 的节点数）。

Answer 2

我的尝试：

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

def findParent(name,parent,tree,found = False):
    if tree == {}:
        return False
    if parent in tree:
        tree[parent][name] = {}
        return True
    else:
        for p in tree:
            found = findParent(name,parent,tree[p],False) or found
        return found

tree = {}
outOfOrder = []
for person in persons:
    if person['parent'] == None:
        tree[person['name']] = {}
    else:
        if not findParent(person['name'],person['parent'],tree):
            outOfOrder.append(person)
for person in outOfOrder:
    if not findParent(person['name'],person['parent'],tree):
        print 'parent of ' + person['name']  + ' not found
print tree

结果：

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

它还会拾取尚未添加父级的所有子级，然后在最后进行协调。

Answer 3

第四次编辑，显示三个版本，整理了一下。第一个版本按照您的要求自上而下和 returns None 工作，但本质上循环遍历顶级数组 3 次。下一个版本只循环一次，但 returns 空字典而不是 None。

最终版本自下而上，非常干净。它可以 return 使用单个循环清空字典，或者 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': {}}}}

使用 children 从字典数组构建嵌套的 tree-like 字典

Build nested tree-like dict from an array of dicts with children

python

arrays

tree

dictionary