基于深度信息的多级dict的dict列表

Question

我有一些数据，或多或少像这样：

[
{"tag": "A", "level":0},
{"tag": "B", "level":1},
{"tag": "D", "level":2},
{"tag": "F", "level":3},
{"tag": "G", "level":4},
{"tag": "E", "level":2},
{"tag": "H", "level":3},
{"tag": "I", "level":3},
{"tag": "C", "level":1},
{"tag": "J", "level":2},
]

我想把它变成一个基于深度级别(关键"级别"(的多级dict:

{
"A": {"level": 0, "children": {
"B": {"level": 1, "children": {
"D": {"level": 2, "children": {
"F": {"level": 3, "children": {
"G": {"level": 4, "children": {}}}}}},
"E": {"level": 2, "children": {
"H": {"level": 3, "children": {}},
"I": {"level": 3, "children": {}}}}}},
"C": {"level": 1, "children": {
"J": {"level": 2, "children": {}}}}}}
}

我现在能想到的就是这段代码。。。在几项之后明显断裂：

def list2multilevel(list):
children = {}
parent = list.pop(0)
tag = parent.get("Tag")
level = parent.get("Level")
for child in list:
ctag = child.get("Tag")
clevel = child.get("Level")
if clevel == level + 1:
children.update(list2multilevel(list))
elif clevel <= level:
print(clevel, level)
break
return {tag: children}

最初是在周五坐下来的，这应该只是一个小练习。。。。

Answer 1

data = [
{"tag": "A", "level": 0},
{"tag": "B", "level": 1},
{"tag": "D", "level": 2},
{"tag": "F", "level": 3},
{"tag": "G", "level": 4},
{"tag": "E", "level": 2},
{"tag": "H", "level": 3},
{"tag": "I", "level": 3},
{"tag": "C", "level": 1},
{"tag": "J", "level": 2},
]
root = {'level': -1, 'children': {}}
parents = {-1: root}
for datum in data:
level = datum['level']
parents[level] = parents[level - 1]['children'][datum['tag']] = {
'level': datum['level'],
'children': {},
}
result = root['children']
print(result)

输出：

{'A': {'level': 0, 'children': {'B': {'level': 1, 'children': {'D': {'level': 2, 'children': {'F': {'level': 3, 'children': {'G': {'level': 4, 'children': {}}}}}}, 'E': {'level': 2, 'children': {'H': {'level': 3, 'children': {}}, 'I': {'level': 3, 'children': {}}}}}}, 'C': {'level': 1, 'children': {'J': {'level': 2, 'children': {}}}}}}}

限制：

• level >= 0
• 任何一个level都不能大于之前出现的最大级别的+1

解释：

• parents是一个字典，用于记住每个级别的最后一个元素
• root是一个起始点(虚设元素(
• 逻辑：
  • 从表示root的-1级别开始
  • 制作一个项并将其注册到父项的children中
  • 将同一项更新到parents字典
  • 重复
  • 提取root['children']

Answer 2

使用递归的其他解决方案(与Boseong Choi的答案限制相同(：

data = [
{"tag": "A", "level": 0},
{"tag": "B", "level": 1},
{"tag": "D", "level": 2},
{"tag": "F", "level": 3},
{"tag": "G", "level": 4},
{"tag": "E", "level": 2},
{"tag": "H", "level": 3},
{"tag": "I", "level": 3},
{"tag": "C", "level": 1},
{"tag": "J", "level": 2},
]
def make_node(dic):
node = dic.copy()
node["children"] = {}
tag = node.pop("tag")
return tag, node
def add_child(parent, child, tag):
assert child["level"] > parent["level"]
if child["level"] == parent["level"] + 1:
parent["children"][tag] = child
return True
for node in parent["children"].values():
if add_child(node, child, tag):
return True
return False
def parse(lst):
assert lst[0]["level"] == 0
root_tag, root = make_node(lst[0])
for item in lst[1:]:
tag, node = make_node(item)
add_child(root, node, tag)

print(parse(data))

Answer 3

您可以使用递归：

from itertools import groupby as gb
data = [{'tag': 'A', 'level': 0}, {'tag': 'B', 'level': 1}, {'tag': 'D', 'level': 2}, {'tag': 'F', 'level': 3}, {'tag': 'G', 'level': 4}, {'tag': 'E', 'level': 2}, {'tag': 'H', 'level': 3}, {'tag': 'I', 'level': 3}, {'tag': 'C', 'level': 1}, {'tag': 'J', 'level': 2}]
def to_tree(d, s = 0):
v = [list(b) for _, b in gb(d, key=lambda x:x['level'] == s)]
if len(v) == 1:
return {i['tag']:{'level':s, 'children':{}} for i in v[0]}
return {v[i][0]['tag']:{'level':s, 'children':to_tree(v[i+1], s+1)} for i in range(0, len(v), 2)}

---

import json
print(json.dumps(to_tree(data), indent=4))

输出：

{
"A": {
"level": 0,
"children": {
"B": {
"level": 1,
"children": {
"D": {
"level": 2,
"children": {
"F": {
"level": 3,
"children": {
"G": {
"level": 4,
"children": {}
}
}
}
}
},
"E": {
"level": 2,
"children": {
"H": {
"level": 3,
"children": {}
},
"I": {
"level": 3,
"children": {}
}
}
}
}
},
"C": {
"level": 1,
"children": {
"J": {
"level": 2,
"children": {}
}
}
}
}
}
}