从一个包含字典的数组中构建嵌套的树形字典，带有子节点。

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数组中。一个项目可能既是子级又是父级。或者一个项目可能只是一个子级（没有自己的子级）。

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

top_parent
  child_one
  child_two
    grand_child

在这个人为简化的例子中，top_parent 是一个父节点但不是子节点；child_one 是一个子节点但不是父节点；child_two 是一个既是父节点也是子节点的节点；grand_child 是一个子节点但不是父节点。这涵盖了所有可能的状态。

我想要做的是能够遍历一次字典数组并生成一个正确表示树结构的嵌套字典（如果只能遍历一次，则以最有效的方式）。因此，在这个例子中，我会得到一个像这样的字典：

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

严格来说，没有子项的条目不需要不作为键，但这是更可取的。

- smargh

---

你想在最终的字典中忽略名称和描述吗？ - Jashaszun

它们可以被忽略，但不需要这样做。关键目标是嵌套字典，以正确表示对象的父子关系。 - smargh

名称是否保证唯一？ - csunday95

是的。名称将是唯一的。这由Web服务保证。 - smargh

BFS或DFS都可以，我猜。每个节点只会被访问一次，你可以按自己喜欢的方式将结果存储在字典中。 - f.rodrigues

你真的只需要一个循环，还是需要O(N)的顺序？ - Patrick Maupin

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': {}}}}

- Patrick Maupin

---

build_bottom_up() 函数，无需使用 None，是最干净的（你说得对）。显然，“魔法”发生在 for 循环内的最后一行。我很想听听您详细解释那里究竟发生了什么。 - smargh

实际上，“魔法”就在defaultdict里面。由于我将dict作为all_dicts值的构造函数传递，因此在任何索引操作中，如果使用常规字典会导致KeyError，defaultdict将构造一个新的默认对象（空字典）并将其添加到字典中。这种行为意味着无论是先遇到父对象还是子对象都没有关系——在任何情况下，都会根据需要构造字典，然后当遇到另一个对象时，相同的字典将可用并被使用。如果这不清楚，我可以再试一次... - Patrick Maupin

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Patrick Maupin

Answer 2

你可以保留一个从名称到节点的惰性映射，然后仅通过处理parent链接来重建层次结构（我假设数据是正确的，所以如果A被标记为B的父级，则当且仅当B被列为A的子级时）。

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 属性仅用于确定该元素是否应在其父元素中作为 None 存储（因为没有子元素），或者是否应该是一个字典，因为它将在重建过程结束时拥有子元素。将没有子元素的节点存储为空字典可以通过避免需要此特殊情况来简化代码。

使用 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)，在输入上只经过一次，并且需要O(N)的空间用于名称->节点映射（原始版本nochildren->None需要Nc个具有子节点的节点，因此空间需求为O(Nc)）。

- 6502

---

我会编辑问题，但None不是必需的值。因此，我希望看到您没有这种限制的简化版本。 - smargh

Answer 3

我的尝试：

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': {}}}

它还会捕捉到任何尚未添加父级的子元素，最后再进行调和。

- csunday95