從Python中的鄰接列表構建菜單樹

Question

考慮一個基本的鄰接列表;節點列表由Node類表示，其屬性爲id,parent_id和name。頂級節點的parent_id = None。

什麼是轉換列表轉換成一個未排序的HTML菜單樹的Python化的方式，如：

• 節點名稱
• 節點名稱
  • 子節點名稱
  • 子節點名稱

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是沒有的（不是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 

Answer 2

這是我最後實現它 - @ thg435的方式是優雅的，但建立字典打印清單。這一次將打印的實際HTML UL菜單樹：

nodes = [ 
{ 'id':1, 'parent_id':None, 'name':'a' }, 
{ 'id':2, 'parent_id':None, 'name':'b' }, 
{ 'id':3, 'parent_id':2, 'name':'c' }, 
{ 'id':4, 'parent_id':2, 'name':'d' }, 
{ 'id':5, 'parent_id':4, 'name':'e' }, 
{ 'id':6, 'parent_id':None, 'name':'f' } 
] 

output = '' 

def build_node(node): 
    global output 
    output += '<li><a>'+node['name']+'</a>' 
    build_nodes(node['id'] 
    output += '</li>' 

def build_nodes(node_parent_id): 
    global output 
    subnodes = [node for node in nodes if node['parent_id'] == node_parent_id] 
    if len(subnodes) > 0 : 
     output += '<ul>' 
     [build_node(subnode) for subnode in subnodes] 
     output += '</ul>' 

build_nodes(None) # Pass in None as a parent id to start with top level nodes 

print output 

你可以在這裏看到：http://ideone.com/34RT4

礦使用遞歸（涼）和全球輸出字符串（不涼）

有人能肯定會對此有所改進，但它現在正在爲我工​​作..