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

Question

我有一个dictionaries从database亲子关系中得到的清单：data = [  {"id":1, "parent_id": 0, "name": "Wood", "price": 0},   {"id":2, "parent_id": 1, "name": "Mango", "price": 18},   {"id":3, "parent_id": 2, "name": "Table", "price": 342},   {"id":4, "parent_id": 2, "name": "Box", "price": 340},   {"id":5, "parent_id": 4, "name": "Pencil", "price": 240},   {"id":6, "parent_id": 0, "name": "Electronic", "price": 20},   {"id":7, "parent_id": 6, "name": "TV", "price": 350},   {"id":8, "parent_id": 6, "name": "Mobile", "price": 300},   {"id":9, "parent_id": 8, "name": "Iphone", "price": 0},   {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}]我想将其转换为嵌套字典，例如[ { "id": 1, "parent_id": 0, "name": "Wood", "price": 0, "children": [ { "id": 2, "parent_id": 1, "name": "Mango", "price": 18, "children": [ { "id": 3, "parent_id": 2, "name": "Table", "price": 342 }, { "id": 4, "parent_id": 2, "name": "Box", "price": 340, "children": [ { "id": 5, "parent_id": 4, "name": "Pencil", "price": 240 } ] } ] } ] }, { "id": 6, "parent_id": 0, "name": "Electronic", "price": 20, "children": [ { "id": 7, "parent_id": 6, "name": "TV", "price": 350 }, { "id": 8, "parent_id": 6, "name": "Mobile", "price": 300, "children": [ { "id": 9, "parent_id": 8, "name": "Iphone", "price": 0, "children": [ { "id": 10, "parent_id": 9, "name": "Iphone 10", "price": 400 } ] } ] } ] } ]

Answer 1

您可以递归地执行此操作，从根节点（where parent_id = 0）开始向下。但是在递归调用之前，您可以按节点对节点进行分组，parent_id以便在每次递归调用中访问它们可以在恒定时间内完成：

levels = {}

for n in data:

    levels.setdefault(n['parent_id'], []).append(n)

def build_tree(parent_id=0):

    nodes = [dict(n) for n in levels.get(parent_id, [])]

    for n in nodes:

        children = build_tree(n['id'])

        if children: n['children'] = children

    return nodes

tree = build_tree()

print(tree)

输出

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0,'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400}]}]}]}]

Answer 2

我制定了一个非常短的解决方案，我相信它不是最有效的算法，但它确实可以完成这项工作，需要进行地狱般的优化才能处理非常大的数据集。

for i in range(len(data)-1, -1, -1):

    data[i]["children"] = [child for child in data if child["parent_id"] == data[i]["id"]]

        for child in data[i]["children"]:

                data.remove(child)

这是完整的解释：

data = [

  {"id":1, "parent_id": 0, "name": "Wood", "price": 0}, 

  {"id":2, "parent_id": 1, "name": "Mango", "price": 18}, 

  {"id":3, "parent_id": 2, "name": "Table", "price": 342}, 

  {"id":4, "parent_id": 2, "name": "Box", "price": 340}, 

  {"id":5, "parent_id": 4, "name": "Pencil", "price": 240}, 

  {"id":6, "parent_id": 0, "name": "Electronic", "price": 20}, 

  {"id":7, "parent_id": 6, "name": "TV", "price": 350}, 

  {"id":8, "parent_id": 6, "name": "Mobile", "price": 300}, 

  {"id":9, "parent_id": 8, "name": "Iphone", "price": 0}, 

  {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}

]

# Looping backwards,placing the lowest child

# into the next parent in the heirarchy

for i in range(len(data)-1, -1, -1):

    # Create a dict key for the current parent in the loop called "children"

    # and assign to it a list comprehension that loops over all items in the data

    # to get the elements which have a parent_id equivalent to our current element's id

    data[i]["children"] = [child for child in data if child["parent_id"] == data[i]["id"]]

    # since the child is placed inside our its parent already, we will

    # remove it from its actual position in the data

    for child in data[i]["children"]:

        data.remove(child)

# print the new data structure      

print(data)

这是输出：

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342, 'children': []}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240, 'children': []}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350, 'children': []}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0, 'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400, 'children': []}]}]}]}]

Answer 3

代码是内联记录的。忽略循环关系等极端情况。

# Actual Data

data = [

  {"id":1, "parent_id": 0, "name": "Wood", "price": 0}, 

  {"id":2, "parent_id": 1, "name": "Mango", "price": 18}, 

  {"id":3, "parent_id": 2, "name": "Table", "price": 342}, 

  {"id":4, "parent_id": 2, "name": "Box", "price": 340}, 

  {"id":5, "parent_id": 4, "name": "Pencil", "price": 240}, 

  {"id":6, "parent_id": 0, "name": "Electronic", "price": 20}, 

  {"id":7, "parent_id": 6, "name": "TV", "price": 350}, 

  {"id":8, "parent_id": 6, "name": "Mobile", "price": 300}, 

  {"id":9, "parent_id": 8, "name": "Iphone", "price": 0}, 

  {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}

]

# Create Parent -> child links using dictonary

data_dict = { r['id'] : r for r in data}

for r in data:

    if r['parent_id'] in data_dict:

        parent = data_dict[r['parent_id']]

        if 'children' not in parent:

            parent['children'] = []

        parent['children'].append(r)

# Helper function to get all the id's associated with a parent

def get_all_ids(r):

    l = list()

    l.append(r['id'])

    if 'children' in r:

        for c in r['children']:

            l.extend(get_all_ids(c))

    return l

# Trimp the results to have a id only once

ids = set(data_dict.keys())

result = []

for r in data_dict.values():

    the_ids = set(get_all_ids(r))

    if ids.intersection(the_ids):

        ids = ids.difference(the_ids)

        result.append(r)

print (result)

输出：

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0, 'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400}]}]}]}]