Python实用代码-无限级分类树状结构生成算法

今日长剑在握 2021-01-21 09:30:31
代码 Python 实用 分类 无限


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

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

图片.png

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

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

[
{"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

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

这里是微信公众号 Python 编程参考,如果你觉得这篇文章对你有帮助,请来关注我哦。点击前往作者专栏 https://www.weishidong.com,看更多有用知识。

版权声明
本文为[今日长剑在握]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000039044208

  1. Python 爬虫进阶 - 前后端分离有什么了不起,过程超详细!
  2. 【python】使用pip提示ModuleNotFoundError
  3. 【python】虚拟环境搭建
  4. Advanced test | Python written test questions
  5. Fire! Open source Python ticket grabbing artifact, come home to see this wave of New Year!
  6. Python crawler advanced - before and after the end of the separation of what great, super detailed process!
  7. [Python] prompt modulenotfounderror with PIP
  8. Building a virtual environment
  9. Serverless 架构下用 Python 轻松搞定图像分类和预测
  10. Easy image classification and prediction with Python under serverless architecture
  11. python协程爬取某网站的老赖数据
  12. Python coroutine crawls Laolai data of a website
  13. 使用Python分析姿态估计数据集COCO的教程
  14. Using Python to analyze the data set coco of attitude estimation
  15. win环境 python3 flask 上手整理 环境搭建(一)
  16. Getting started with win environment python3 flash
  17. Python实现一个论文下载器,赶紧收藏
  18. win环境 python3 flask 上手整理 快速上手-基础操作(二)
  19. Python 中常见的配置文件写法
  20. Python to achieve a paper Downloader, quickly collect
  21. Python批量 png转ico
  22. 使用line_profiler对python代码性能进行评估优化
  23. 使用line_profiler对python代码性能进行评估优化
  24. Getting started with Python 3 flash in win environment
  25. Common ways to write configuration files in Python
  26. Python会在2021年死去吗? Python 3.9最终版本的回顾
  27. Python batch PNG to ICO
  28. Using line_ Profiler evaluates and optimizes the performance of Python code
  29. Using line_ Profiler evaluates and optimizes the performance of Python code
  30. Will Python die in 2021? A review of the final version of Python 3.9
  31. Python3 SMTP send mail
  32. Understanding closures in Python: getting started with closures
  33. Python日志实践
  34. Python logging practice
  35. [python opencv 计算机视觉零基础到实战] 十、图片效果毛玻璃
  36. [python opencv 计算机视觉零基础到实战] 九、模糊
  37. 10. Picture effect ground glass
  38. [Python opencv computer vision zero basis to actual combat] 9. Fuzzy
  39. 使用line_profiler對python程式碼效能進行評估優化
  40. Using line_ Profiler to evaluate and optimize the performance of Python code
  41. LeetCode | 0508. 出现次数最多的子树元素和【Python】
  42. Leetcode | 0508
  43. LeetCode | 0530. 二叉搜索树的最小绝对差【Python】
  44. LeetCode | 0515. 在每个树行中找最大值【Python】
  45. Leetcode | 0530. Minimum absolute difference of binary search tree [Python]
  46. Leetcode | 0515. Find the maximum value in each tree row [Python]
  47. 我来记笔记啦-搭建python虚拟环境
  48. Let me take notes - building a python virtual environment
  49. LeetCode | 0513. 找树左下角的值【Python】
  50. Leetcode | 0513. Find the value in the lower left corner of the tree [Python]
  51. Python OpenCV 泛洪填充,取经之旅第 21 天
  52. Python opencv flood fill, day 21
  53. Python爬虫自学系列(二)
  54. Python crawler self study series (2)
  55. 【python】身份证号码有效性检验
  56. [Python] validity test of ID number
  57. Python ORM - pymysql&sqlalchemy
  58. Python ORM - pymysql&sqlalchemy
  59. centos7 安装python3.8
  60. centos7 安装python3.8