Python 无限级分类树状结构生成算法的实现

脚本专栏 2024/11/19 佚名

3 1 2

后端研发的同学对无限级分类肯定映像深刻，当初花了不少时间吧？

无限级分类树状结构的应用场景很多，例如后端研发需要把用户相关权限读取出来并生成树状结构，前端研发拿到权限树之后可以按照结构展示用户有权限访问的栏目；再例如网页上的栏目分级：

作者在初次接触树状结构生成需求的时候，也是挠头，后来找到了一个代码少且清晰易懂的生成算法：递归。

首先，确保数据库中存储的类别信息如下：

[
 {"id": 1, "name": '电器', "parent": 0},
 {"id": 2, "name": '水果', "parent": 0},
 {"id": 3, "name": '家用电器', "parent": 1},
 {"id": 4, "name": '电吹风', "parent": 3},
 {"id": 5, "name": '电风扇', "parent": 3},
 {"id": 6, "name": '台灯', "parent": 3},
 {"id": 7, "name": '商用电器', "parent": 1},
 {"id": 8, "name": '大型电热锅', "parent": 7},
]

字段 parent 记录的是此条目的父编号，例如电吹风的父编号是 3，即电吹风属于家用电器，而家用电器的父编号是 1，即家用电器属于电器类产品。电吹风条目跟电器条目并无直接的标识进行关联，但需要用树状结构来表明电器 <- 家用电器 <- 电吹风的关系。

通过 parent 寻找父编号，并建立关联关系的操作实际上是循环往复的，直到找完所有的结点，这跟递归算法非常契合，很轻松便能写出对应的递归代码：

def generate_tree(source, parent):
 tree = []
 for item in source:
 if item["parent"] == parent:
 item["child"] = generate_tree(source, item["id"])
 tree.append(item)
 return tree

只需要将数据库中存储的信息传递给 generate_tree 函数即可。这段递归代码在往复循环的过程中通过 parent 来寻找子结点，找到子结点后将其添加到树中。完整代码如下：

import json
def generate_tree(source, parent):
 tree = []
 for item in source:
 if item["parent"] == parent:
 item["child"] = generate_tree(source, item["id"])
 tree.append(item)
 return tree
if __name__ == '__main__':
 permission_source = [
 {"id": 1, "name": '电器', "parent": 0},
 {"id": 2, "name": '水果', "parent": 0},
 {"id": 3, "name": '家用电器', "parent": 1},
 {"id": 4, "name": '电吹风', "parent": 2},
 {"id": 5, "name": '电风扇', "parent": 3},
 {"id": 6, "name": '台灯', "parent": 3},
 {"id": 7, "name": '商用电器', "parent": 1},
 {"id": 8, "name": '大型电热锅', "parent": 7},
 ]
 permission_tree = generate_tree(permission_source, 0)
 print(json.dumps(permission_tree, ensure_ascii=False))

你试试运行一下，看看结构是否符合预期。

使用缓存优化算法

递归算法中有很多重复的计算，这些计算不仅占用额外资源，还会降低函数执行效率，因此需要对递归进行优化。这里选用缓存优化法提升函数执行效率。

基本思路是每次找到结点关系后将此条目的编号添加到一个列表中缓存起来，代表此条目已找到结点关系。当往复循环执行函数时再次遇到此条目可以跳过。代码改动很简单，增加一个缓存列表和控制流语句即可：

def generate_tree(source, parent, cache=[]):
 tree = []
 for item in source:
 if item["id"] in cache:
 continue
 if item["parent"] == parent:
 cache.append(item["id"])
 item["child"] = generate_tree(source, item["id"], cache)
 tree.append(item)
 return tree

至此，无限级分类树状结构生成算法完成。你学会了吗？

Python,无限级分类树状结构,Python,,树状结构

华山资源网 Design By www.eoogi.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

华山资源网 Design By www.eoogi.com

评论“Python 无限级分类树状结构生成算法的实现”

暂无评论...

www.eoogi.com 华山资源网

120,135影音资源

344,641技术资源

22,817软件资源

435,032站长资源

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

2024年11月19日

Python 无限级分类树状结构生成算法的实现

使用缓存优化算法

python Scrapy爬虫框架的使用

python 可视化库PyG2Plot的使用

评论“Python 无限级分类树状结构生成算法的实现”

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

更新日志

友情链接