一次性搞定權(quán)限樹遍歷（通用解決方案）

一、權(quán)限樹是什么

在寫項目的權(quán)限管理模塊、用戶系統(tǒng)的時候經(jīng)常碰見類似的樹結(jié)構(gòu)我們一般習慣稱之為權(quán)限樹，權(quán)限樹應用的地方有很多，比較常見的有：權(quán)限管理時候的樹狀圖（如上圖），頁面左側(cè)的一二三級的菜單，物品分類的樹狀菜單。

在實際項目中這種權(quán)限結(jié)構(gòu)，數(shù)據(jù)庫設(shè)計一般是這樣的：

其中我們需要通過id和父id來遍歷樹狀圖，這種結(jié)構(gòu)非常簡單也很好理解，但對于新手編碼來說就不是特別的友好了，特別是培訓出來的朋友可能對數(shù)據(jù)結(jié)構(gòu)和算法不是特別了解，經(jīng)常性會參考網(wǎng)上一些不是很優(yōu)秀的寫法，通過遞歸的方式反復的查詢數(shù)據(jù)庫來逐層往上級遍歷，這種寫法的運行起來比較慢，網(wǎng)絡(luò)開銷比較大，如下圖：

二、如何遍歷權(quán)限樹

下面我們一起思考如何寫一個權(quán)限樹的遍歷并且讓其適用與大部分情況

1、設(shè)計結(jié)構(gòu)

根據(jù)上文數(shù)據(jù)庫，可以設(shè)計出一個簡單有效的結(jié)構(gòu)：

• data：數(shù)據(jù)庫表的任意一行權(quán)限

• childrenNode：data節(jié)點下所有的權(quán)限集合

然后添加上get、set方法，為了方便再增加兩個構(gòu)造函數(shù)，用于對元素初始化（空構(gòu)造函數(shù)也不忘記），因為我們無法得知data具體是什么類型，所有使用泛型讓data可以成為任何類，增加通用性。

public?class?TreeNode<T>?{
????//數(shù)據(jù)內(nèi)容
????private?T?data;
????//這個節(jié)點下的子節(jié)點
????private?List>?childrenNode?=?new?ArrayList<>();
?
????public?T?getData()?{
????????return?data;
????}
?
????public?void?setData(T?data)?{
????????this.data?=?data;
????}
?
????public?List>?getChildrenNode()?{
????????return?childrenNode;
????}
?
????public?void?setChildrenNode(List>?childrenNode)?{
????????this.childrenNode?=?childrenNode;
????}
?
????public?TreeNode(T?data,?List>?childrenNode)?{
????????this.data?=?data;
????????this.childrenNode?=?childrenNode;
????}
?
????public?TreeNode()?{
????}
}

2、獲取權(quán)限數(shù)據(jù)

之前說到反復的去數(shù)據(jù)庫獲取數(shù)據(jù)會讓網(wǎng)絡(luò)開銷變大，所以我們應該一次性將所有需要的權(quán)限數(shù)據(jù)全部取出（有的時候是取出全部的數(shù)據(jù)，有時取得某個角色的權(quán)限數(shù)據(jù)），將取到數(shù)據(jù)放入一個list中。

一個節(jié)點類應該還具有獲取自己子節(jié)點的能力，在TreeNode類中添加獲取子節(jié)點方法：

通過data的id和每條數(shù)據(jù)的父id對比相同的放入子節(jié)點的集合中，并且從數(shù)據(jù)集合中刪除（這樣做只要權(quán)限數(shù)據(jù)集合變成空了就可以算是樹遍歷完成）

public?List>?childrenNode(List?datas,?String?idName,?String?fidName)?{
????????ConvertTree?convertTree?=?new?ConvertTree<>();
????????String?idValue?=?convertTree.getFieldValue(data,?idName);
????????List?collect?=?datas.stream()
????????????????.filter(date?->?idValue.equals(convertTree.getFieldValue(date,?fidName)))
????????????????.collect(Collectors.toList());
????????datas.removeAll(collect);
????????for?(T?node?:?collect)?{
????????????TreeNode?treeNode?=?new?TreeNode<>();
????????????treeNode.setData(node);
????????????childrenNode.add(treeNode);
????????}
????????return?childrenNode;
????}

由于無法知道具體的類也就不知道id字段和父id字段，采用反射的方式獲取字段的值

public?String?getFieldValue(T?o,?String?fieldName)?{
????????//得到class
????????Class?cls?=?o.getClass();
????????//得到所有屬性
????????Field[]?fields?=?cls.getDeclaredFields();
????????for?(Field?field?:?fields)?{
????????????try?{
????????????????//打開私有訪問
????????????????field.setAccessible(true);
????????????????//獲取屬性
????????????????if?(field.getName().equals(fieldName))?{
????????????????????Object?result?=?field.get(o);
????????????????????if?(result?==?null)?{
????????????????????????return?null;
????????????????????}
????????????????????return?result.toString();
????????????????}
????????????}?catch?(IllegalAccessException?e)?{
????????????????e.printStackTrace();
????????????}
????????}
????????throw?new?RuntimeException("獲取屬性值失敗");
????}

3、從數(shù)據(jù)中找出根節(jié)點

我們首先需要定位一棵樹最頂端的節(jié)點，也就是根節(jié)點“祖宗節(jié)點”。

新建一個類，并添加獲取根節(jié)點方法。這個方法需要權(quán)限數(shù)據(jù)的集合，id的字段名，父id的字段名

思路：判斷權(quán)限集合是否為空，取出集合中第一個元素，用過遞歸一層一層往上找，一直到找不到父節(jié)點為止，將這個得到的根節(jié)放到我們的樹結(jié)構(gòu)中，并且通過childrenNode來獲取子節(jié)點他的子節(jié)點。

private?TreeNode?getRootNode(List?datas,?String?idName,?String?fidName)?{
????????if?(datas.isEmpty())?{
????????????return?null;
????????}
????????T?node?=?datas.get(0);
????????T?rootNode?=?getRootNode(datas,?idName,?fidName,?node);
????????TreeNode?rootTreeNode?=?new?TreeNode<>();
????????datas.remove(rootNode);
????????rootTreeNode.setData(rootNode);
????????rootTreeNode.childrenNode(datas,?idName,?fidName);
????????return?rootTreeNode;
????}

這個方法會不停的遞歸直到早不到父節(jié)點為止

private?T?getRootNode(List?datas,?String?idName,?String?fidName,?T?node)?{
????????T?fNode?=?null;
????????String?fieldValue?=?getFieldValue(node,?fidName);
????????for?(T?data?:?datas)?{
????????????if?(getFieldValue(data,?idName).equals(fieldValue))?{
????????????????fNode?=?data;
????????????????break;
????????????}
????????}
????????if?(fNode?==?null)?{
????????????return?node;
????????}?else?{
????????????return?getRootNode(datas,?idName,?fidName,?fNode);
????????}
????}

4、根據(jù)根節(jié)點形成一棵樹

先獲取根節(jié)點，然后使用forChildren方法遍歷根節(jié)點的子集，一級一級的往下查找子級，最后返回樹。

private?TreeNode?getTree(List?datas,?String?idName,?String?fidName)?{
????????//獲取樹根
????????TreeNode?rootNode?=?getRootNode(datas,?idName,?fidName);
????????//遍歷樹根的子集
????????List>?childrenNode?=?rootNode.getChildrenNode();
????????forChildren(datas,?idName,?fidName,?childrenNode);
????????//此時樹已經(jīng)形成
????????return?rootNode;
????}

遍歷子集，將子集的子集記錄下來，存入needForList，如果needForList不為空就一直遞歸，needForList為空的時候說明這棵樹的所有相關(guān)的節(jié)點都找到了并且都通過childrenNode方法處理成TreeNode類。

private?void?forChildren(List?datas,?String?idName,?String?fidName,?List>?childrenNode)?{
????????//需要遍歷的集合
????????List>?needForList?=?new?ArrayList<>();
????????for?(TreeNode?tTreeNode?:?childrenNode)?{
????????????List>?treeNodes?=?tTreeNode.childrenNode(datas,?idName,?fidName);
????????????needForList.addAll(treeNodes);
????????}
????????if?(!needForList.isEmpty())?{
????????????forChildren(datas,?idName,?fidName,?needForList);
????????}
????}

三、形成森林

很多時候權(quán)限樹并沒有一個統(tǒng)一的根節(jié)點，如下圖：

系統(tǒng)管理、軟件管理、統(tǒng)計分析各是一棵樹，這時候我們就需要把每一棵樹都遍歷出來，添加形成森林的方法：

只需要循環(huán)執(zhí)行形成樹的方法，一直到所有的權(quán)限數(shù)據(jù)的集合為空的時候結(jié)束，將所有的遍歷出來的樹放入集合中，返回集合。

public?List>?getForest(List?datas,?String?idName,?String?fidName)?{
????????List>?forest?=?new?ArrayList<>();
????????while?(!datas.isEmpty())?{
????????????TreeNode?tree?=?getTree(datas,?idName,?fidName);
????????????forest.add(tree);
????????}
????????return?forest;
????}

四、使用

1.僅支持java8，id不可重復

2.調(diào)用方法就可以使用了

public?List>?toTree()?{
????????//獲取數(shù)據(jù)集合
????????List?list?=?authResourceRepository.findAll();
????????//創(chuàng)建工具類
????????ConvertTree?convertTree?=?new?ConvertTree<>();
????????//生成森林
????????List>?forest?=?convertTree.getForest(list,?"id",?"parentId");
????????return?convertTree.getForest(list);
????}

3.代碼：

https://github.com/guoyixing/converttree