从 Python 中的邻接列表构建菜单树

Question

考虑一个基本的邻接表；节点的列表由节点类代表，具有属性id，parent_id和name。顶级节点的parent_id = None。

将列表转换为无序 html 菜单树的 Pythonic 方式是什么，例如：

• 节点名
• 节点名
  • 子节点名称
  • 子节点名称

Answer 1

假设你有这样的事情：

data = [

    { 'id': 1, 'parent_id': 2, 'name': "Node1" },
    { 'id': 2, 'parent_id': 5, 'name': "Node2" },
    { 'id': 3, 'parent_id': 0, 'name': "Node3" },
    { 'id': 4, 'parent_id': 5, 'name': "Node4" },
    { 'id': 5, 'parent_id': 0, 'name': "Node5" },
    { 'id': 6, 'parent_id': 3, 'name': "Node6" },
    { 'id': 7, 'parent_id': 3, 'name': "Node7" },
    { 'id': 8, 'parent_id': 0, 'name': "Node8" },
    { 'id': 9, 'parent_id': 1, 'name': "Node9" }
]

此函数遍历列表并创建树，收集每个节点的子节点是sub列表：

def list_to_tree(data):
    out = { 
        0: { 'id': 0, 'parent_id': 0, 'name': "Root node", 'sub': [] }
    }

    for p in data:
        out.setdefault(p['parent_id'], { 'sub': [] })
        out.setdefault(p['id'], { 'sub': [] })
        out[p['id']].update(p)
        out[p['parent_id']]['sub'].append(out[p['id']])

    return out[0]

例子：

tree = list_to_tree(data)
import pprint
pprint.pprint(tree)

如果父 ID 为 None（不是 0），请像这样修改函数：

def list_to_tree(data):
    out = {
        'root': { 'id': 0, 'parent_id': 0, 'name': "Root node", 'sub': [] }
    }

    for p in data:
        pid = p['parent_id'] or 'root'
        out.setdefault(pid, { 'sub': [] })
        out.setdefault(p['id'], { 'sub': [] })
        out[p['id']].update(p)
        out[pid]['sub'].append(out[p['id']])

    return out['root']
    # or return out['root']['sub'] to return the list of root nodes