Python infinite classification tree structure generation algorithm "practical code"

Sleeping devil's lies 2021-01-21 15:49:07
python infinite classification tree structure


There are many applications of infinite level classification tree structure , For example, back-end R & D needs to read out the user's relevant permissions and generate a tree structure , After the front-end R & D gets the permission tree, it can display the columns that users have permission to access according to the structure ; Another example is the column classification on the web page :  picture .png When the author first came into contact with tree structure generation requirements , It's also scratching your head , Later, I found a generation algorithm with less code and clear and easy to understand : recursive .

First , Make sure that the category information stored in the database is as follows :

[
{"id": 1, "name": ' Electrical appliances ', "parent": 0},
{"id": 2, "name": ' Fruits ', "parent": 0},
{"id": 3, "name": ' Household appliances ', "parent": 1},
{"id": 4, "name": ' hair drier ', "parent": 3},
{"id": 5, "name": ' Electric fan ', "parent": 3},
{"id": 6, "name": ' Desk lamp ', "parent": 3},
{"id": 7, "name": ' Commercial electrical appliances ', "parent": 1},
{"id": 8, "name": ' Large electric cooker ', "parent": 7},
]

Field parent  The parent number of this entry is recorded , For example, the parent number of a hair dryer is 3, The hair dryer belongs to household appliances , And the parent number of household appliances is 1, That is, household appliances belong to electrical products . The entry of hair dryer is not directly associated with the entry of electrical appliances , But you need to use a tree structure to show Electrical appliances <- Household appliances <- hair drier   The relationship between .

adopt parent  Find parent number , And the operation of establishing association is actually cyclical , Until all the nodes are found , This fits well with recursive algorithms , Very easy to write the corresponding recursive code :

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 

Just pass the information stored in the database to generate_tree  Function . This piece of recursive code passes through in a reciprocating loop parent  To find the child nodes , Find the child node and add it to the tree . The complete code is as follows :

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": ' Electrical appliances ', "parent": 0},
{"id": 2, "name": ' Fruits ', "parent": 0},
{"id": 3, "name": ' Household appliances ', "parent": 1},
{"id": 4, "name": ' hair drier ', "parent": 2},
{"id": 5, "name": ' Electric fan ', "parent": 3},
{"id": 6, "name": ' Desk lamp ', "parent": 3},
{"id": 7, "name": ' Commercial electrical appliances ', "parent": 1},
{"id": 8, "name": ' Large electric cooker ', "parent": 7},
]
permission_tree = generate_tree(permission_source, 0)
print(json.dumps(permission_tree, ensure_ascii=False)) 

The output result of the terminal is shown in the figure below : Untitled.jpeg

Use the cache optimization algorithm

There are a lot of repeated calculations in recursive algorithms , These calculations not only take up extra resources , It also reduces the efficiency of function execution , So we need to optimize recursion . Here, cache optimization method is used to improve the efficiency of function execution .

The basic idea is to add the number of this entry to a list to cache after finding the node relationship , Represents that this entry has found a node relationship . If you encounter this entry again when you execute the function in a reciprocating loop, you can skip . The code changes are simple , Add a cache list and control flow statement :

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 

thus , Infinite level classification tree structure generation algorithm is completed . Have you learned ?

author : Students of the chief swordsmanship teacher of the state of Qin

版权声明
本文为[Sleeping devil's lies]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/01/20210121154833637G.html

  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