如何将字典列表转换为像嵌套字典一样的树

Question

我有这种格式的数据 -

data = {
    "label": "xyz.com",
    "children": [
        {
            "parent": "abc.com",
            "label": "user-3",
            "depth": 1
        },
        {
            "parent": "xyz.com",
            "label": "abc.com",
            "depth": 0
        },
        {
            "parent": "xyz.com",
            "label": "user-1",
            "depth": 0
        }
    ]
}

我想生成一个看起来像这样的结果(嵌套字典(-

result = {
    "label": "xyz.com",
    "children": [
         {
             "parent": "xyz.com",
             "label": "user-1",
             "depth": 0
         },
        {
            "parent": "xyz.com",
            "label": "abc.com",
            "depth": 0,
            "children": [
                {
                    "parent": "abc.com",
                    "label": "user-3",
                    "depth": 1
                }
            ]
         }
    ]
}

初始字典使用标签 - 父级和深度转换为嵌套词典。

此外，可以有任意数量的儿童。例如-

result = {
    "lable": "xyz.com",
    "children": [
         {
             "parent": "xyz.com",
             "label": "user-1",
             "depth": 0
         },
        {
            "parent": "xyz.com",
            "label": "abc.com",
            "depth": 0,
            "children": [
                {
                    "parent": "abc.com",
                    "label": "user-3",
                    "depth": 1,
                    "children": [
                        {...}, {...}
                    ]
                }
            ]
         }
    ]
}

不确定递归是否是要走的路，或者还有其他解决方案。

感谢您的帮助。

Answer 1

一种更有效的单程线性方法是构建一个将标签映射到节点的字典，以便您只需在字典中查找父节点的标签即可轻松获取父节点，并将节点附加到父节点的children子列表中。如果迭代早于父节点到达子节点，则使用 dict.setdefault 首先初始化父节点的字典条目，以便父节点稍后可以使用预先存在的children条目更新自身：

result = {'label': data['label']}
nodes = {data['label']: result}
for node in data['children']:
    node.update(nodes.get(node['label'], {}))
    nodes[node['label']] = node
    nodes.setdefault(node['parent'], {}).setdefault('children', []).append(node)

result变成：

{'label': 'xyz.com',
 'children': [{'parent': 'xyz.com',
               'label': 'abc.com',
               'depth': 0,
               'children': [{'parent': 'abc.com',
                             'label': 'user-3',
                             'depth': 1}]},
              {'parent': 'xyz.com', 'label': 'user-1', 'depth': 0}]}

Answer 2

您可以使用递归：

data = {'label': 'xyz.com', 'children': [{'parent': 'abc.com', 'label': 'user-3', 'depth': 1}, {'parent': 'xyz.com', 'label': 'abc.com', 'depth': 0}, {'parent': 'xyz.com', 'label': 'user-1', 'depth': 0}]}
def group(d):
  new_d = [i for i in d if all(c.get('label') != i.get('parent') for c in d)]
  c = [(lambda x:{a:b for a, b in x.items() if a != 'children' or b})({**i, 'children':[*i.get('children', []), *[j for j in d if j.get('parent') == i['label']]]}) for i in new_d]
  return [i if 'children' not in i else {**i, 'children':group(i['children'])} for i in c]

---

import json
print(json.dumps(group([data]), indent=4))

输出：

[
  {
    "label": "xyz.com",
    "children": [
        {
            "parent": "xyz.com",
            "label": "abc.com",
            "depth": 0,
            "children": [
                {
                    "parent": "abc.com",
                    "label": "user-3",
                    "depth": 1
                }
            ]
        },
        {
            "parent": "xyz.com",
            "label": "user-1",
            "depth": 0
        }
      ]
   }
]

Answer 3

递归方法的更简单实现是利用字典中已有的键并改变字典，而不是创建新的字典：

def convert(nodes, parent):
    children = [convert(nodes, node) for node in nodes if node['parent'] == parent['label']]
    if children:
        parent['children'] = children
    return parent

以便convert(data.pop('children'), data)返回：

{'label': 'xyz.com',
 'children': [{'parent': 'xyz.com',
               'label': 'abc.com',
               'depth': 0,
               'children': [{'parent': 'abc.com',
                             'label': 'user-3',
                             'depth': 1}]},
              {'parent': 'xyz.com', 'label': 'user-1', 'depth': 0}]}