文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-04-02 19:55

关注

本篇文章给大家分享的是有关Python如何实现无限级分类树状结构生成算法,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

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

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

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

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

[  {"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,即家用电器属于电器类产品。电吹风条目跟电器条目并无直接的标识进行关联,但需要用树状结构来表明 电器 <- 家用电器 <- 电吹风 的关系。

版权水印 微信公众号 Python 编程参考

通过 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

至此,无限级分类树状结构生成算法完成。


阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯