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

睡魔的谎言 2021-01-21 15:48:46
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,即家用电器属于电器类产品。电吹风条目跟电器条目并无直接的标识进行关联,但需要用树状结构来表明 电器 <- 家用电器 <- 电吹风  的关系。

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

终端输出结果如下图所示: Untitled.jpeg

使用缓存优化算法

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

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

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 

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

作者:秦国首席剑术教师的学生

版权声明
本文为[睡魔的谎言]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000039050506

  1. LeetCode | 0508. 出现次数最多的子树元素和【Python】
  2. Leetcode | 0508
  3. LeetCode | 0530. 二叉搜索树的最小绝对差【Python】
  4. LeetCode | 0515. 在每个树行中找最大值【Python】
  5. Leetcode | 0530. Minimum absolute difference of binary search tree [Python]
  6. Leetcode | 0515. Find the maximum value in each tree row [Python]
  7. 我来记笔记啦-搭建python虚拟环境
  8. Let me take notes - building a python virtual environment
  9. LeetCode | 0513. 找树左下角的值【Python】
  10. Leetcode | 0513. Find the value in the lower left corner of the tree [Python]
  11. Python OpenCV 泛洪填充,取经之旅第 21 天
  12. Python opencv flood fill, day 21
  13. Python爬虫自学系列(二)
  14. Python crawler self study series (2)
  15. 【python】身份证号码有效性检验
  16. [Python] validity test of ID number
  17. Python ORM - pymysql&sqlalchemy
  18. Python ORM - pymysql&sqlalchemy
  19. centos7 安装python3.8
  20. centos7 安装python3.8
  21. Centos7 installing Python 3.8
  22. Centos7 installing Python 3.8
  23. Django——图书管理系统(六)
  24. Django——图书管理系统(五)
  25. Django -- library management system (6)
  26. Django -- library management system (5)
  27. python批量插入数据小脚本
  28. Python batch insert data script
  29. ZoomEye-python 使用指南
  30. Zoomeye Python User's Guide
  31. 用Python写代码,一分钟搞定一天工作量,同事直呼:好家伙 - 知乎
  32. Using Python to write code, one minute to complete a day's workload, colleagues call: good guy - Zhihu
  33. Python 上的可视化库——PyG2Plot
  34. Pyg2plot: a visualization library on Python
  35. Python 上的可视化库——PyG2Plot
  36. Python实用代码-无限级分类树状结构生成算法
  37. Pyg2plot: a visualization library on Python
  38. Python utility code - infinite classification tree structure generation algorithm
  39. 奇技淫巧,还是正统功夫?Python推导式最全用法
  40. Pandas 的这个知识点,估计 80% 的人都得挂!
  41. 前后端分离有什么了不起,手把手教你用Python爬下来!
  42. 在 Azure 上执行一些简单的 python 工作
  43. 推荐 :利用Python的混合集成机器学习(附链接)
  44. Cunning or orthodox Kung Fu? The most complete usage of Python derivation
  45. It's estimated that 80% of pandas people have to hang up!
  46. What's so great about the separation of front and rear ends? Hand in hand teach you to climb down with Python!
  47. Doing some simple Python work on azure
  48. Recommendation: hybrid integrated machine learning using python (link attached)
  49. Learning PPO algorithm programming from scratch (Python version)
  50. Python OpenCV 图片模糊操作 blur 与 medianBlur
  51. Python OpenCV image blur operation blur and mediablur
  52. 成功解决cv2.error: OpenCV(4.1.2) C:\projects\opencv-python\opencv\modules\imgproc\src\color.cpp:182: err
  53. Cv2.error solved successfully: opencv (4.1.2) C:: (projects / opencv Python / opencv modules / imgproc / SRC)\ color.cpp:182 : err
  54. Python 中使用 virtualenv 管理虚拟环境
  55. Using virtualenv to manage virtual environment in Python
  56. 如何使用Python执行系统命令?Python学习教程!
  57. How to use Python to execute system commands? Python tutorial!
  58. 快速掌握Python中的循环技术
  59. Quickly grasp the loop technology in Python
  60. Python主流Web框架之Tornado