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

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

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

首先，確保資料庫中儲存的類別資訊如下：

[ {"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 jsondef generate_tree(source, parent): tree = [] for item in source: if item["parent"] == parent: item["child"] = generate_tree(source, item["id"]) tree.append(item) return treeif __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

至此，無限級分類樹狀結構生成演算法完成。你學會了嗎？