python 树形菜单无限极分类怎样实现？

Question

数据结构：

create table web_class (
    "id" integer NOT NULL PRIMARY KEY AUTOINCREMENT,
    "name" varchar(255) NOT NULL,         --名称
    "bid" integer,                        --上级ID
)

数据库数据：
{id:1, name:'名称1', bid:0}
{id:2, name:'名称2', bid:0}
{id:3, name:'名称3', bid:1}
{id:4, name:'名称4', bid:1}
{id:5, name:'名称5', bid:3}
{id:6, name:'名称6', bid:5}
...

需要实现的树形菜单(类似如下)：

[{'bid':0,'id':1,'name':'名称1',
    'son':[
        {'bid':1,'id':3,'name':'名称3',
            'son':[
               {'bid':3,'id':5,'name':'名称5',
                   'son':[
                       {'bid':3,'id':6,'name':'名称6','son':[]}
                   ]
               }
            ]
        },
        {'bid':1,'id':4,'name':'名称4','son':[]}
    ]
},
{'bid':0,'id':2,'name':'名称2','son':[]}]

如能讲解下原理最好了。

Answer 1

我自己研究写出来的一个函数（线型菜单转树形菜单）：

def xTree(datas):
    lists=[]
    tree={}
    parent_id=''
    for i in datas:
        item=i
        tree[item['id']]=item
    root=None
    for i in datas:
        obj=i
        if not obj['bid']:
            root=tree[obj['id']]
            lists.append(root)
        else:
            parent_id=obj['bid']
            if 'children' not in tree[parent_id]:   
                tree[parent_id]['children']=[]
            tree[parent_id]['children'].append(tree[obj['id']])
    return lists
print(xTree(data))

Answer 2

#从你的数据库中查出数据，如下格式
l = [{"id":1, "name":'名称1', "bid":0},
{"id":2, "name":'名称2', "bid":0},
{"id":3, "name":'名称3', "bid":1},
{"id":4, "name":'名称4', "bid":1},
{"id":5, "name":'名称5', "bid":3},
{"id":6, "name":'名称6', "bid":5}]
l.insert(0, {"id": 0, "name": "root"}) #插入根节点
for i in l:
    i["son"] = []


#建立索引
index = {l[i]["id"] : i for i in range(len(l))}

for i in range(1, len(l)):
    l[index[l[i]["bid"]]]["son"].append(l[i]) # l[i]的bid索引对应的节点，添加子节点l[i]
    # bid = l[i]["bid"] 取出bid
    # i0 = index[bid] 通过索引得到bid的index
    # l[i0]就是父节点
    # l[i0]["son"].append(l[i]) 父节点添加子节点
    

print(l[0]["son"]) #输出结果

Answer 3

data = [{"id":1, "name":'名称1', "bid":0},
{"id":2, "name":'名称2', "bid":0},
{"id":3, "name":'名称3', "bid":1},
{"id":4, "name":'名称4', "bid":1},
{"id":5, "name":'名称5', "bid":3},
{"id":6, "name":'名称6', "bid":5}]
new_data =[] # 定义一个与 data 一模一样的新列表
d_data = [] # 定义一个最终需要的列表

for d in data:
    d["son"] = []
    new_data.append(d)
# 先为每一个元素，也就是每一个字典增加一个 key="son"

son_id = [] # 定义一个元素为所有子元素的 id 的列表
    
for d in data:
    for nd in new_data: # 双层循环，寻求用笛卡尔积的模式来实现子节点嵌套
        if d["id"]  == nd["bid"]: # 如果一个元素的 bid 与另一个元素的 id 相同
            d["son"].append(nd)   # 就将另一个元素设为该元素的 “son” 键的值
            son_id.append(nd["id"]) # 将子元素的 id 记录到 son_id 列表
    if d["id"] not in son_id:     # 在外层循环中判断该元素的 id 是否在 son_id 列表中
        d_data.append(d) # 如果不是，则将该元素添加到最终目标的 d_data 列表中
    
    
        
print(d_data)

实现结果如下：

[{'id': 1, 'name': '名称1', 'bid': 0, 'son': [{'id': 3, 'name': '名称3', 'bid': 1, 'son': [{'id': 5, 'name': '名称5', 'bid': 3, 'son': [{'id': 6, 'name': '名称6', 'bid': 5, 'son': []}]}]}, {'id': 4, 'name': '名称4', 'bid': 1, 'son': []}]}, {'id': 2, 'name': '名称2', 'bid': 0, 'son': []}]

树形展开：

[{'id': 1, 'name': '名称1', 'bid': 0, 
'son': [
           {'id': 3, 'name': '名称3', 'bid': 1, 
           'son': [
                   {'id': 5, 'name': '名称5', 'bid': 3, 
                   'son': [
                              {'id': 6, 'name': '名称6', 'bid': 5, 'son': []}
                          ]
                   }
                   ]
           }, 
           {'id': 4, 'name': '名称4', 'bid': 1, 'son': []}
       ]
 }, 
{'id': 2, 'name': '名称2', 'bid': 0, 'son': []}]

期望大侠们能给出更 pythonic 的代码。

Answer 4

不是python程序员，不过分享一些对于树形结构的研究。
如果你用的数据库支持层次化查询最好。比如Oracle的Connect By或者其他数据库的CTE.由数据库帮你计算Level, Path, IS_LEAF最好，否者利用程序去实现Lazy Load会比较麻烦。对于CTE的支持现在越来越普及了，可以考虑。

数据库中实现树形结构有两种方式：adjacent list和nested set。一般都是前者

Answer 5

class BaseCategoryTree(BaseService):

def __init__(self, db):
    self.db = db
    self.category_tree = []

def create_tree(self, parent):
    parent['children'] = []
    for record in self.category_tree:
        if str(record['parent_id']) == str(parent['id']):
            parent['children'].append(self.create_tree(record))
    return parent

def get_category_trees(self, **kwargs):
    """

    :return:
    """
    category_base_svr = ErpBcategoryService(self.db)

    category_list ='你的所有列表'

    self.category_tree = [i.to_dict() for i in category_list]
    comment_tree = []
    for record in self.category_tree:
        if str(record['parent_id']) == '0':  # if this is the start of a tree
            comment_tree.append(self.create_tree(record))
    return comment_tree