后端研發(fā)的同學(xué)對(duì)無(wú)限級(jí)分類肯定映像深刻，當(dāng)初花了不少時(shí)間吧？

無(wú)限級(jí)分類樹(shù)狀結(jié)構(gòu)的應(yīng)用場(chǎng)景很多，例如后端研發(fā)需要把用戶相關(guān)權(quán)限讀取出來(lái)并生成樹(shù)狀結(jié)構(gòu)，前端研發(fā)拿到權(quán)限樹(shù)之后可以按照結(jié)構(gòu)展示用戶有權(quán)限訪問(wèn)的欄目；再例如網(wǎng)頁(yè)上的欄目分級(jí)：

作者在初次接觸樹(shù)狀結(jié)構(gòu)生成需求的時(shí)候，也是撓頭，后來(lái)找到了一個(gè)代碼少且清晰易懂的生成算法：遞歸。

首先，確保數(shù)據(jù)庫(kù)中存儲(chǔ)的類別信息如下：

[ {'id': 1, 'name': ’電器’, 'parent': 0}, {'id': 2, 'name': ’水果’, 'parent': 0}, {'id': 3, 'name': ’家用電器’, 'parent': 1}, {'id': 4, 'name': ’電吹風(fēng)’, 'parent': 3}, {'id': 5, 'name': ’電風(fēng)扇’, 'parent': 3}, {'id': 6, 'name': ’臺(tái)燈’, 'parent': 3}, {'id': 7, 'name': ’商用電器’, 'parent': 1}, {'id': 8, 'name': ’大型電熱鍋’, 'parent': 7},]

字段 parent 記錄的是此條目的父編號(hào)，例如電吹風(fēng)的父編號(hào)是 3，即電吹風(fēng)屬于家用電器，而家用電器的父編號(hào)是 1，即家用電器屬于電器類產(chǎn)品。電吹風(fēng)條目跟電器條目并無(wú)直接的標(biāo)識(shí)進(jìn)行關(guān)聯(lián)，但需要用樹(shù)狀結(jié)構(gòu)來(lái)表明 電器 <- 家用電器 <- 電吹風(fēng) 的關(guān)系。

通過(guò) parent 尋找父編號(hào)，并建立關(guān)聯(lián)關(guān)系的操作實(shí)際上是循環(huán)往復(fù)的，直到找完所有的結(jié)點(diǎn)，這跟遞歸算法非常契合，很輕松便能寫出對(duì)應(yīng)的遞歸代碼：

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ù)庫(kù)中存儲(chǔ)的信息傳遞給 generate_tree 函數(shù)即可。這段遞歸代碼在往復(fù)循環(huán)的過(guò)程中通過(guò) parent 來(lái)尋找子結(jié)點(diǎn)，找到子結(jié)點(diǎn)后將其添加到樹(shù)中。完整代碼如下：

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': ’電吹風(fēng)’, 'parent': 2}, {'id': 5, 'name': ’電風(fēng)扇’, 'parent': 3}, {'id': 6, 'name': ’臺(tái)燈’, '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))

你試試運(yùn)行一下，看看結(jié)構(gòu)是否符合預(yù)期。

遞歸算法中有很多重復(fù)的計(jì)算，這些計(jì)算不僅占用額外資源，還會(huì)降低函數(shù)執(zhí)行效率，因此需要對(duì)遞歸進(jìn)行優(yōu)化。這里選用緩存優(yōu)化法提升函數(shù)執(zhí)行效率。

基本思路是每次找到結(jié)點(diǎn)關(guān)系后將此條目的編號(hào)添加到一個(gè)列表中緩存起來(lái)，代表此條目已找到結(jié)點(diǎn)關(guān)系。當(dāng)往復(fù)循環(huán)執(zhí)行函數(shù)時(shí)再次遇到此條目可以跳過(guò)。代碼改動(dòng)很簡(jiǎn)單，增加一個(gè)緩存列表和控制流語(yǔ)句即可：

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

至此，無(wú)限級(jí)分類樹(shù)狀結(jié)構(gòu)生成算法完成。你學(xué)會(huì)了嗎？

到此這篇關(guān)于Python 無(wú)限級(jí)分類樹(shù)狀結(jié)構(gòu)生成算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Python 無(wú)限級(jí)分類樹(shù)狀結(jié)構(gòu)內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！