Python如何實(shí)現(xiàn)無限級分類樹狀結(jié)構(gòu)生成算法

本篇文章給大家分享的是有關(guān)Python如何實(shí)現(xiàn)無限級分類樹狀結(jié)構(gòu)生成算法，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

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

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

首先，確保數(shù)據(jù)庫中存儲(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": '臺燈', "parent": 3},  {"id": 7, "name": '商用電器', "parent": 1},  {"id": 8, "name": '大型電熱鍋', "parent": 7}, ]

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

版權(quán)水印 微信公眾號 Python 編程參考

通過 parent 尋找父編號，并建立關(guān)聯(lián)關(guān)系的操作實(shí)際上是循環(huán)往復(fù)的，直到找完所有的結(jié)點(diǎn)，這跟遞歸算法非常契合，很輕松便能寫出對應(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ù)庫中存儲(chǔ)的信息傳遞給 generate_tree 函數(shù)即可。這段遞歸代碼在往復(fù)循環(huán)的過程中通過 parent 來尋找子結(jié)點(diǎn)，找到子結(jié)點(diǎn)后將其添加到樹中。完整代碼如下：

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": '電吹風(fēng)', "parent": 2},  {"id": 5, "name": '電風(fēng)扇', "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))

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

使用緩存優(yōu)化算法

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

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

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)生成算法完成。