无限分类树结构有很多应用场景，比如后端研发需要读取用户相关权限生成树结构，前端研发有权限树之后，可以根据结构展示用户可以访问的列；再比如网页上的栏目分类：笔者刚开始接触树结构生成需求时，摸不着头脑，后来发现了一个清晰易懂的代码很少的生成算法：递归。首先确定数据库中存储的类目信息如下：[{"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},]字段父记录为该条目的父编号，例如吹风机的父编号为3，即吹风机属于家电，家电的父编号为1，即，家用电器属于电器产品。电吹风项和电器项之间没有直接标识，需要用树形结构来表示电器<-家用电器<-电吹风的关系。通过parent找到父编号并建立关系的操作其实就是一个循环，直到找到所有的节点。这很符合递归算法，很容易写出相应的递归代码：defgenerate_tree(source,parent):tree=[]foriteminsource:ifitem["parent"]==parent:item["child"]=generate_tree(source,item["id"])tree.append(item)returntreeonly你需要将存储在数据库中的信息传递给generate_tree函数。这段递归代码在往复循环的过程中使用parent寻找子节点，找到子节点后添加到树中。完整代码如下：importjsondefgenerate_tree(source,parent):tree=[]foriteminsource:ifitem["parent"]==parent:item["child"]=generate_tree(source,item["id"])tree.append(item)returntreeif__name__=='__main__':permission_source=[{"id":1,"name":'Appliance',"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))终端输出结果如下图所示：使用缓存优化算法重复计算较多递归算法，而这些计算不仅占用额外的资源，也会降低函数执行的效率，所以递归需要优化。这里采用缓存优化的方法来提高函数的执行效率。基本思路是，每找到一个节点关系，就把这个表项的编号加到一个链表中缓存起来，也就是说这个表项找到了一个节点关系。当功能以往复循环执行时，可以跳过此条目。代码修改很简单，只需要添加缓存列表和控制流语句：defgenerate_tree(source,parent,cache=[]):tree=[]foriteminsource:ifitem["id"]incache:continue如果item["parent"]==parent:cache.append(item["id"])item["child"]=generate_tree(source,item["id"],cache)tree.append(item)返回树至此，无限类分类树结构生成算法完成。你学会了吗？作者：秦国首席剑术师弟子
