关于算法: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，即家用电器属于电器类产品。电吹风条目跟电器条目并无间接的标识进行关联，但须要用树状构造来表明电器 <- 家用电器 <- 电吹风的关系。

版权水印微信公众号 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，看更多有用常识。

应用缓存优化算法