一、權(quán)限樹是什么
在寫項(xiàng)目的權(quán)限管理模塊、用戶系統(tǒng)的時候經(jīng)常碰見類似的樹結(jié)構(gòu)我們一般習(xí)慣稱之為權(quán)限樹，權(quán)限樹應(yīng)用的地方有很多，比較常見的有：權(quán)限管理時候的樹狀圖（如上圖），頁面左側(cè)的一二三級的菜單，物品分類的樹狀菜單。
在實(shí)際項(xiàng)目中這種權(quán)限結(jié)構(gòu)，數(shù)據(jù)庫設(shè)計(jì)一般是這樣的：
其中我們需要通過id和父id來遍歷樹狀圖，這種結(jié)構(gòu)非常簡單也很好理解，但對于新手編碼來說就不是特別的友好了，特別是培訓(xùn)出來的朋友可能對數(shù)據(jù)結(jié)構(gòu)和算法不是特別了解，經(jīng)常性會參考網(wǎng)上一些不是很優(yōu)秀的寫法，通過遞歸的方式反復(fù)的查詢數(shù)據(jù)庫來逐層往上級遍歷，這種寫法的運(yùn)行起來比較慢，網(wǎng)絡(luò)開銷比較大，如下圖：
二、如何遍歷權(quán)限樹
下面我們一起思考如何寫一個權(quán)限樹的遍歷并且讓其適用與大部分情況
1、設(shè)計(jì)結(jié)構(gòu)
根據(jù)上文數(shù)據(jù)庫，可以設(shè)計(jì)出一個簡單有效的結(jié)構(gòu)：
- data：數(shù)據(jù)庫表的任意一行權(quán)限
- childrenNode：data節(jié)點(diǎn)下所有的權(quán)限集合
然后添加上get、set方法，為了方便再增加兩個構(gòu)造函數(shù)，用于對元素初始化（空構(gòu)造函數(shù)也不忘記），因?yàn)槲覀儫o法得知data具體是什么類型，所有使用泛型讓data可以成為任何類，增加通用性。
public class TreeNode<T> {
//數(shù)據(jù)內(nèi)容
private T data;
//這個節(jié)點(diǎn)下的子節(jié)點(diǎn)
private List<TreeNode<T>> childrenNode = new ArrayList<>();
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public List<TreeNode<T>> getChildrenNode() {
return childrenNode;
}
public void setChildrenNode(List<TreeNode<T>> childrenNode) {
this.childrenNode = childrenNode;
}
public TreeNode(T data, List<TreeNode<T>> childrenNode) {
this.data = data;
this.childrenNode = childrenNode;
}
public TreeNode() {
}
}
2、獲取權(quán)限數(shù)據(jù)
之前說到反復(fù)的去數(shù)據(jù)庫獲取數(shù)據(jù)會讓網(wǎng)絡(luò)開銷變大，所以我們應(yīng)該一次性將所有需要的權(quán)限數(shù)據(jù)全部取出（有的時候是取出全部的數(shù)據(jù)，有時取得某個角色的權(quán)限數(shù)據(jù)），將取到數(shù)據(jù)放入一個list中。
一個節(jié)點(diǎn)類應(yīng)該還具有獲取自己子節(jié)點(diǎn)的能力，在TreeNode類中添加獲取子節(jié)點(diǎn)方法：
通過data的id和每條數(shù)據(jù)的父id對比相同的放入子節(jié)點(diǎn)的集合中，并且從數(shù)據(jù)集合中刪除（這樣做只要權(quán)限數(shù)據(jù)集合變成空了就可以算是樹遍歷完成）
public List<TreeNode<T>> childrenNode(List<T> datas, String idName, String fidName) {
ConvertTree<T> convertTree = new ConvertTree<>();
String idValue = convertTree.getFieldValue(data, idName);
List<T> collect = datas.stream()
.filter(date -> idValue.equals(convertTree.getFieldValue(date, fidName)))
.collect(Collectors.toList());
datas.removeAll(collect);
for (T node : collect) {
TreeNode<T> 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é)點(diǎn)
我們首先需要定位一棵樹最頂端的節(jié)點(diǎn)，也就是根節(jié)點(diǎn)“祖宗節(jié)點(diǎn)”。
新建一個類，并添加獲取根節(jié)點(diǎn)方法。這個方法需要權(quán)限數(shù)據(jù)的集合，id的字段名，父id的字段名
思路：判斷權(quán)限集合是否為空，取出集合中第一個元素，用過遞歸一層一層往上找，一直到找不到父節(jié)點(diǎn)為止，將這個得到的根節(jié)放到我們的樹結(jié)構(gòu)中，并且通過childrenNode來獲取子節(jié)點(diǎn)他的子節(jié)點(diǎn)。
private TreeNode<T> getRootNode(List<T> datas, String idName, String fidName) {
if (datas.isEmpty()) {
return null;
}
T node = datas.get(0);
T rootNode = getRootNode(datas, idName, fidName, node);
TreeNode<T> rootTreeNode = new TreeNode<>();
datas.remove(rootNode);
rootTreeNode.setData(rootNode);
rootTreeNode.childrenNode(datas, idName, fidName);
return rootTreeNode;
}
這個方法會不停的遞歸直到早不到父節(jié)點(diǎn)為止
private T getRootNode(List<T> 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é)點(diǎn)形成一棵樹
先獲取根節(jié)點(diǎn)，然后使用forChildren方法遍歷根節(jié)點(diǎn)的子集，一級一級的往下查找子級，最后返回樹。
private TreeNode<T> getTree(List<T> datas, String idName, String fidName) {
//獲取樹根
TreeNode<T> rootNode = getRootNode(datas, idName, fidName);
//遍歷樹根的子集
List<TreeNode<T>> childrenNode = rootNode.getChildrenNode();
forChildren(datas, idName, fidName, childrenNode);
//此時樹已經(jīng)形成
return rootNode;
}
遍歷子集，將子集的子集記錄下來，存入needForList，如果needForList不為空就一直遞歸，needForList為空的時候說明這棵樹的所有相關(guān)的節(jié)點(diǎn)都找到了并且都通過childrenNode方法處理成TreeNode類。
private void forChildren(List<T> datas, String idName, String fidName, List<TreeNode<T>> childrenNode) {
//需要遍歷的集合
List<TreeNode<T>> needForList = new ArrayList<>();
for (TreeNode<T> tTreeNode : childrenNode) {
List<TreeNode<T>> treeNodes = tTreeNode.childrenNode(datas, idName, fidName);
needForList.addAll(treeNodes);
}
if (!needForList.isEmpty()) {
forChildren(datas, idName, fidName, needForList);
}
}
三、形成森林
很多時候權(quán)限樹并沒有一個統(tǒng)一的根節(jié)點(diǎn)，如下圖：
系統(tǒng)管理、軟件管理、統(tǒng)計(jì)分析各是一棵樹，這時候我們就需要把每一棵樹都遍歷出來，添加形成森林的方法：
只需要循環(huán)執(zhí)行形成樹的方法，一直到所有的權(quán)限數(shù)據(jù)的集合為空的時候結(jié)束，將所有的遍歷出來的樹放入集合中，返回集合。
public List<TreeNode<T>> getForest(List<T> datas, String idName, String fidName) {
List<TreeNode<T>> forest = new ArrayList<>();
while (!datas.isEmpty()) {
TreeNode<T> tree = getTree(datas, idName, fidName);
forest.add(tree);
}
return forest;
}
四、使用
1.僅支持java8，id不可重復(fù)
2.調(diào)用方法就可以使用了
public List<TreeNode<AuthResource>> toTree() {
//獲取數(shù)據(jù)集合
List<AuthResource> list = authResourceRepository.findAll();
//創(chuàng)建工具類
ConvertTree<AuthResource> convertTree = new ConvertTree<>();
//生成森林
List<TreeNode<AuthResource>> forest = convertTree.getForest(list, "id", "parentId");
return convertTree.getForest(list);
}
3.代碼：
