怎么在Python中生成一个无限级分类树状结构生成算法

发布时间:2021-01-22 14:52:48 作者:Leah
来源:亿速云 阅读:253

今天就跟大家聊聊有关怎么在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,即家用电器属于电器类产品。电吹风条目跟电器条目并无直接的标识进行关联,但需要用树状结构来表明 电器 <- 家用电器 <- 电吹风 的关系。

通过 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中生成一个无限级分类树状结构生成算法有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。

推荐阅读:
  1. 使用python怎么生成一个多层json结构
  2. 怎么在python中实现一个树状嵌套结构

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:小程序中有没有立即执行函数

下一篇:django如何在python项目中使用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》