建立一个多文档形式的词典

Question

我从数据库对象中获取，这些对象是在树中排序的数据库的目录项：

db_tree = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]

该列表已按树排序，即有一个父节（级别1），如果有子节，则为第1级的下一节。我需要把这些数据带到这种字典里：

tree = {}
tree['parent 1'] = {}
tree['parent 1']['child 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1']['child 4 levl parent 1'] = {}
tree['parent 1']['child 1 - 2'] = {}
tree['parent 1']['child 1 - 2']['children 2- 1'] = {}
tree['parent 1']['child 1- 3'] = {}
tree['parent 1']['child1']['child3'] = {} 

tree['parent 2'] = {}
tree['parent 2']['parent 2- 1 - chil'] = {}

tree['parent 3'] = {}
tree['parent 4'] = {}

如果有人遇到或做了这件事，请告诉我

Answer 1

您可以跟踪ID到它在树中的位置的映射，以及实际树的另一个映射。你知道吗

db_tree = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]

tree = {}
id_to_children = {1: tree}


for entry in db_tree:
    id = entry["id"]
    name = entry["name"]
    parent_id = entry["parent_id"]
    # assume all elements are new, could check if it already exists
    my_children = {}
    id_to_children[id] = my_children
    #this is where we should be added in the tree.
    parent_children = id_to_children[parent_id]
    # add our node as a new child of our parent.
    parent_children[name] = my_children


import pprint

pprint.pprint(tree)

Answer 2

我将递归地构建tree：

from pprint import pprint


def process_row(row, index, tree):
    if row is None:
        return tree
    parent = index.get(row["parent_id"], None)
    subtree = process_row(parent, index, tree)
    if row["name"] not in subtree:
        subtree[row["name"]] = {}
    return subtree[row["name"]]


def build_tree(db_tree):
    tree = {}
    index = {row["id"]: row for row in db_tree}
    for row in db_tree:
        process_row(row, index, tree)
    return tree


db_tree = [
    {"id": 2, "parent_id": 1, "level": 1,  "name": "parent 1"},
    {"id": 5, "parent_id": 2, "level": 2,  "name": "child 1 - 1"},
    {"id": 6, "parent_id": 2, "level": 2,  "name": "child 1 - 2"},
    {"id": 9, "parent_id": 2, "level": 2,  "name": "child 1- 3"},
    {"id": 7, "parent_id": 5, "level": 3,  "name": "child 1 - 1 - 1"},
    {"id": 11, "parent_id": 6, "level": 3, "name": "children 2- 1"},
    {"id": 10, "parent_id": 7, "level": 4, "name": "child 4 levl parent 1"},
    {"id": 3, "parent_id": 1, "level": 1,  "name": "parent 2"},
    {"id": 13, "parent_id": 3, "level": 2, "name": "parent 2- 1 - chil"},
    {"id": 4, "parent_id": 1, "level": 1,  "name": "parent 3"},
    {"id": 8, "parent_id": 1, "level": 1,  "name": "parent 4"},
]

tree = build_tree(db_tree)
pprint(tree)

输出：

{'parent 1': {'child 1 - 1': {'child 1 - 1 - 1': {'child 4 levl parent 1': {}}},
              'child 1 - 2': {'children 2- 1': {}},
              'child 1- 3': {}},
 'parent 2': {'parent 2- 1 - chil': {}},
 'parent 3': {},
 'parent 4': {}}

Answer 3

要获得更好的代码可编性和可视化效果，可以使用networkx的优点：

import networkx as nx
import pprint
G = nx.DiGraph()
for n in db_tree:
    G.add_node(n["name"]) #adds node
    children = [x for x in db_tree if x["id"] == n["parent_id"]]
    if children:
        G.add_edge(n["name"], children[0]["name"]) #add directed edge if it has
nx.draw(G, with_labels=True)

不幸的是，它没有简单的方法将图形转换为嵌套字典的数据结构。你知道吗

输出：