Python utility code - infinite classification tree structure generation algorithm

Long sword in hand today 2021-01-21 09:38:52
python utility code infinite classification


The students of back-end R & D must have a deep impression on infinite level classification , It took a lot of time to be a beginner ?

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 .

Copyright watermark WeChat official account Python Programming reference

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

You try to run it , See if the structure is as expected .

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 ?

This is WeChat official account. Python Programming reference , If you think this article will help you , Please pay attention to me . Click to go to the author column https://www.weishidong.com, See more useful knowledge .

版权声明
本文为[Long sword in hand today]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/01/20210121093016141x.html

  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