后端研發(fā)的同學對無限級分類肯定映像深刻，當初花了不少時間吧？
無限級分類樹狀結(jié)構(gòu)的應用場景很多，例如后端研發(fā)需要把用戶相關(guān)權(quán)限讀取出來并生成樹狀結(jié)構(gòu)，前端研發(fā)拿到權(quán)限樹之后可以按照結(jié)構(gòu)展示用戶有權(quán)限訪問的欄目；再例如網(wǎng)頁上的欄目分級：
作者在初次接觸樹狀結(jié)構(gòu)生成需求的時候，也是撓頭，后來找到了一個代碼少且清晰易懂的生成算法：遞歸。
首先，確保數(shù)據(jù)庫中存儲的類別信息如下：
|
1
2
3
4
5
6
7
8
9
10
|
[ {"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，即家用電器屬于電器類產(chǎn)品。電吹風條目跟電器條目并無直接的標識進行關(guān)聯(lián)，但需要用樹狀結(jié)構(gòu)來表明 電器 <- 家用電器 <- 電吹風 的關(guān)系。
通過 parent 尋找父編號，并建立關(guān)聯(lián)關(guān)系的操作實際上是循環(huán)往復的，直到找完所有的結(jié)點，這跟遞歸算法非常契合，很輕松便能寫出對應的遞歸代碼：
|
1
2
3
4
5
6
7
|
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 |
只需要將數(shù)據(jù)庫中存儲的信息傳遞給 generate_tree 函數(shù)即可。這段遞歸代碼在往復循環(huán)的過程中通過 parent 來尋找子結(jié)點，找到子結(jié)點后將其添加到樹中。完整代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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)) |
你試試運行一下，看看結(jié)構(gòu)是否符合預期。
使用緩存優(yōu)化算法
遞歸算法中有很多重復的計算，這些計算不僅占用額外資源，還會降低函數(shù)執(zhí)行效率，因此需要對遞歸進行優(yōu)化。這里選用緩存優(yōu)化法提升函數(shù)執(zhí)行效率。
基本思路是每次找到結(jié)點關(guān)系后將此條目的編號添加到一個列表中緩存起來，代表此條目已找到結(jié)點關(guān)系。當往復循環(huán)執(zhí)行函數(shù)時再次遇到此條目可以跳過。代碼改動很簡單，增加一個緩存列表和控制流語句即可：
|
1
2
3
4
5
6
7
8
9
10
|
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 |
至此，無限級分類樹狀結(jié)構(gòu)生成算法完成。你學會了嗎？
到此這篇關(guān)于python 無限級分類樹狀結(jié)構(gòu)生成算法的實現(xiàn)的文章就介紹到這了,更多相關(guān)python 無限級分類樹狀結(jié)構(gòu)內(nèi)容請搜索服務器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務器之家！
原文鏈接：https://segmentfault.com/a/1190000039044208
