Python 無限級分類樹狀結構生成算法的實現

Posted on by

後端研發的同學對無限級分類肯定映像深刻，當初花瞭不少時間吧？

無限級分類樹狀結構的應用場景很多，例如後端研發需要把用戶相關權限讀取出來並生成樹狀結構，前端研發拿到權限樹之後可以按照結構展示用戶有權限訪問的欄目；再例如網頁上的欄目分級：

作者在初次接觸樹狀結構生成需求的時候，也是撓頭，後來找到瞭一個代碼少且清晰易懂的生成算法：遞歸。

首先，確保數據庫中存儲的類別信息如下：

[
 {"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 無限級分類樹狀結構生成算法的實現的文章就介紹到這瞭,更多相關Python 無限級分類樹狀結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：