Построение дерева меню из списка смежности в Python - PullRequest
Новая
       36

Построение дерева меню из списка смежности в Python

1 голос
/ 19 ноября 2011

Рассмотрим базовый список смежности;список узлов, представленных классом Node, со свойствами id, parent_id и name.Parent_id узлов верхнего уровня = Нет.

Какой бы Pythonic способ преобразовал список в неупорядоченное дерево HTML-меню, например:

  • имя узла
  • имя узла
    • имя подузла
    • имя подузла

Ответы [ 2 ]

4 голосов
/ 19 ноября 2011

Предполагая, что у вас есть что-то вроде этого: 

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)

Если родительские идентификаторы равны 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
1 голос
/ 20 ноября 2011

Вот так я и реализовал его - способ @ 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

Мой использует рекурсию (круто) и глобальную строку вывода (не круто)

Кто-то наверняка может улучшить это, но у меня это работает прямо сейчас ..

...