将父子字典列表转换为嵌套字典

Question

针对上述问题，我尝试并看到了多种解决方案，但找不到适合我的情况的解决方案。我有以下词典列表。

[
        {"id": "101", "logical_section": "ORGANIZATION", "parent_section_id": None},
        {"id": "102", "logical_section": "ORG_NAMES", "parent_section_id": "101"},
        {"id": "103", "logical_section": "ORG_ADDRESSES", "parent_section_id": "101"},
        {"id": "104", "logical_section": "SOURCEADDRESS", "parent_section_id": "103"},
        {"id": "105", "logical_section": "STANDARDIZEDADDRESS", "parent_section_id": "103"},
        {"id": "106", "logical_section": "ORG_EMPLOYES", "parent_section_id": "101"}
]

我需要按以下方式将此列表转换为嵌套字典列表

{
    "id": "101",
    "logical_section": "ORGANIZATION",
    "parent_section_id": None,
    "child": [
        {
            "id": "102",
            "logical_section": "ORG_NAMES",
            "parent_section_id": "101"
        },
        {
            "id": "103",
            "logical_section": "ORG_ADDRESSES",
            "parent_section_id": "101",
            "child": [
                {"id": "104", "logical_section": "SOURCEADDRESS", "parent_section_id": "103"},
                {"id": "105", "logical_section": "STANDARDIZEDADDRESS", "parent_section_id": "103"}
            ]
        },
        {
            "id": "106",
            "logical_section": "ORG_EMPLOYES",
            "parent_section_id": "101"}
    ]
}

我试过的解决方法如下

levels = dict()
for n in test:
    levels.setdefault(n['parent_section_id'], []).append(n)

但这并没有给出我正在寻找的输出。

如有任何帮助，我们将不胜感激。

Answer 1

我看了一下这个并想出了下面的代码。我绝对确定这可以做得更好：我不建议将它用于大量数据。如果另一个更有经验的程序员可以考虑这个解决方案，我将不胜感激。

test = [
    {"id": "101", "logical_section": "ORGANIZATION", "parent_section_id": None},
    {"id": "102", "logical_section": "ORG_NAMES", "parent_section_id": "101"},
    {"id": "103", "logical_section": "ORG_ADDRESSES", "parent_section_id": "101"},
    {"id": "104", "logical_section": "SOURCEADDRESS", "parent_section_id": "103"},
    {"id": "105", "logical_section": "STANDARDIZEDADDRESS", "parent_section_id": "103"},
    {"id": "106", "logical_section": "ORG_EMPLOYES", "parent_section_id": "101"}
]

ans_dict = test[0]


def insert(tree, node):
    if node["parent_section_id"] == tree["id"]:
        if "child" not in tree:
            tree["child"] = [node]
        else:
            tree["child"].append(node)
    elif "child" in tree:
        for c in tree["child"]:
            insert(c, node)


for record in test:
    insert(ans_dict, record)


print(ans_dict)

此代码使用递归二叉树方法。使它如此低效的原因是每个单个节点都具有 insert() 函数运行并将给定节点作为参数，每次插入新节点时。

Answer 2

这种方法使用广度优先搜索算法来构造树。请注意，由于字典是可变的，因此输入列表中的所有元素都将被修改。您需要 select one/s 其中“parent_section_id”是 None 才能找到所有 parents.

test = [
        {"id": "101", "logical_section": "ORGANIZATION", "parent_section_id": None},
        {"id": "102", "logical_section": "ORG_NAMES", "parent_section_id": "101"},
        {"id": "103", "logical_section": "ORG_ADDRESSES", "parent_section_id": "101"},
        {"id": "104", "logical_section": "SOURCEADDRESS", "parent_section_id": "103"},
        {"id": "105", "logical_section": "STANDARDIZEDADDRESS", "parent_section_id": "103"},
        {"id": "106", "logical_section": "ORG_EMPLOYES", "parent_section_id": "101"}
]

# No assumption about the position of the parent
nodes = [i for i in test if i["parent_section_id"] is None]
# Single parent
parent_idx = test.index(nodes[0])
# If more than 1 parent, then uncomment
#parent_idxs = [test.index(node) for node in nodes]

# Find all children
parent_id_vals = set([d["parent_section_id"] for d in test if d["parent_section_id"] is not None])

while nodes:
    focus_node = nodes[0]
    
    if focus_node["id"] in parent_id_vals:
        focus_node["child"] = []
    
    # Uncomment else clause if "test" is too large
    #else:
    #    nodes.remove(focus_node)
    #    continue
    
    for i in test:
        if i["parent_section_id"] == focus_node["id"]:
            focus_node["child"].append(i)
            nodes.append(i)
    
    nodes.remove(focus_node)
            
# If single parent node
ans = test[parent_idx]
# If multiple parents, then uncomment
#ans = [test[idx] for idx in parent_idxs]

print(ans)

我把这个作为一个小挑战来做。无论如何，DCoxshall 的回答都适合您的需要。

将父子字典列表转换为嵌套字典

Converting parent & child dictionary list to nested dictionary

python

dictionary

tree

nested

hierarchy