同一段程式碼寫N遍？通用樹結構一次搞定

阿里妹導讀

本文深入探討了樹形結構在實際應用中的廣泛使用及其重要性，並提出了一套通用且高效的工具類TreeUtil來處理與樹形資料相關的操作。

前言

樹形結構在我們生活和工作中隨處可見，如資料夾文件、商品分類、審批流程、層級架構等。其資料結構是透過某種對映來組織物件的上下級關係，使這些物件形成樹形層級，常見的應用場景包括：

電商分類：根據不同的型別劃分商品，便於使用者快速查詢需要的產品。
系統選單和許可權多級分類： 後臺系統選單、功能、許可權一般是層級化的，透過樹形結構便於呈現和管理各個選單項。
評論回覆： 樹形結構可以用來顯示帖子回覆的關係，這有助於檢視討論的脈絡。
資料夾目錄：作業系統中的資料夾和檔案透過樹形層級結構進行組織和顯示，以便使用者操作。
業務審批流程：在職級架構中，樹形結構有助於展示和管理各個流程節點及其展示上下級層級關係。

樹形結構其本質是根據某種層級關係對資料列表進行抽象展示。此應用可顯著提升資料的組織和展示效率，使使用者更直觀地理解和高效獲取資訊。

電商分類中的應用

作業系統資料夾結構

許可權管控（RBAC）模型樹

背景：同一段程式碼寫N遍？每個專案都要寫？

在最近在業務開發中，使用者和後臺管理端介面內需要展示本地生活架構下各個BU的全部專案、產品、業務、許可權、投入分類多個域的樹資訊，它們雖然儲存於資料庫獨立底表但是都有極其相似的屬性（如名稱，id，父級id對映值等）。在根據業務場景構建不同的查詢條件從各自資料庫中查詢後，封裝成樹結構返回。如果是單獨為每一個域寫一個封裝樹的方法，那麼會有多個幾乎一模一樣的方法散落在不同的地方，為此構建一個通用的樹工具類是十分必要的。
每個業務專案中都在重複的寫這些操縱樹的方法，造成冗餘和重複“造輪子”。因此一些常用的健壯的對樹的操縱，包括樹構建、排序、搜尋、遍歷等，可以抽取出來封裝到公共元件供其他業務專案使用。

方案選擇

使用Map

Map構建樹demo

public List<Menu> buildTree(List<Menu> list) { ArrayList<Menu> res = new ArrayList<>();// 建立一個Map，以id為鍵 Map<Integer, Menu> dtoMap = new HashMap<>();for (Menu dto : list) { dto.setSubMenus(new ArrayList<>()); // 初始化每個節點的children列表 dtoMap.put(dto.getId(), dto); }// 遍歷列表，將每個節點新增到其父節點的children列表中for (Menu menu : list) { Menu parent = dtoMap.get(menu.getParentId());if (parent != null) { parent.getSubMenus().add(menu); }// 從根節點開始構建樹，假設根節點的parentId為0if (NumberUtils.INTEGER_ZERO.equals(menu.getParentId())) { res.add(menu); } }return res;}

使用Map空間換時間的思路其實並不複雜，主要有三步：

1.每一個節點以id為key，物件為value構建Map

2.遍歷原List，找到父節點時將自身新增到父節點的subMenus裡面去

3.如果此節點是根節點，新增到返回列表中

該方法雖對單一表實體類列表轉樹結構簡單高效，但針對不同實體類需複製相同程式碼，僅替換特定類名如將 Menu 改為 Menu1。此外，若另一表實體類根節點的 parentId 是 null、-1 或其他非零值，或父級 ID 屬性及子集合屬性命名不同，則現有方法缺乏通用性和靈活性。

因此，為了使得封裝樹的方法更通用，工具類下的方法都需要使用簡單健壯的泛型+函式式介面來接收入參和出參。

使用遞迴

遞迴構建樹demo

publicstatic List<Menu> recursiveTree(List<Menu> menus, int parentId) { List<Menu> result = new ArrayList<>();for (Menu menu : menus) {if (menu.getParentId().equals(parentId)) {// 遞迴查詢子選單 menu.setSubMenus(recursiveTree(menus, menu.getId())); result.add(menu); } }return result; }

使用遞迴行數雖然較少，但是我們會發現大量無效的迴圈被使用和可讀性差的問題，不推薦。

效能對比測試

常用的列表轉樹我們一般採用Map構建樹或者遞迴構建樹（較少使用）的演算法來實現，前者用空間來換時間後者則相反，那麼哪種效果會更好一點呢，我們分別對1萬、2萬、3萬、4萬、5萬、6萬個節點進行構建樹耗時測試對比：

本地測試取平均值，不同機器、不同環境下可能會有不同的耗時時間（僅供參考）

透過對比可以看出遞迴實現耗時會隨著節點增長呈指數增長，使用Map構建樹的耗時就小的多了。顯而易見，效能不在一個數量級而且使用遞迴時極有可能因為資料或者程式碼原因出現死迴圈，所以非特殊情況儘量選擇Map構建樹的策略。

TreeUtil工具包方法

如上文所說，為了使得所有方法更通用，工具類下的方法都需要使用簡單健壯的泛型+函式式介面來接收入參和出參。

常見的函式式介面

Java 8自帶了一些常用的函式式介面，位於java.util.function包中：

Function<T, R>：接受一個引數，返回一個結果。
Consumer<T>：接受一個引數，沒有返回值。
Supplier<T>：不接受引數，返回一個結果。
Predicate<T>：接受一個引數，返回一個boolean值。
UnaryOperator<T>：接受和返回同類型的物件。
BinaryOperator<T>：接受兩個相同型別的引數並返回相同型別的結果。

1.標準化介面減少了開發者自己定義類似介面的需要，並且提高了程式碼的可移植性和複用性。

2.提高程式碼的功能擴充套件性，透過組合不同的函式式介面，可以輕鬆地擴充套件和修改功能，而無需對現有的程式碼進行大量改動。

3.函式式介面為API設計提供了更靈活的選項。API使用者可以透過傳遞Lambda表示式或方法引用來自定義行為，使API更加通用和實用。

構建樹makeTree()方法

通用構建樹方法

/** * 構建樹 * * @param menuList 需要合成樹的List * @param pIdGetter 物件中獲取父級ID方法,如:Menu:getParentId * @param idGetter 物件中獲取主鍵ID方法 ,如：Menu:getId

     * @param rootCheck      判斷物件是否根節點的方法，如： x->x.getParentId()==null,x->x.getParentMenuId()==0

* @param setSubChildren 物件中設定下級資料列表方法，如： Menu::setSubMenus */

publicstatic <T, E> List<E> makeTree(List<E> menuList, Function<E, T> pIdGetter, Function<E, T> idGetter, Predicate<E> rootCheck, BiConsumer<E, List<E>> setSubChildren) {

Map<T, List<E>> parentMenuMap = new HashMap<>();for (E node : menuList) {//獲取父節點id T parentId = pIdGetter.apply(node);//節點放入父節點的value內 parentMenuMap.computeIfAbsent(parentId, k -> new ArrayList<>()).add(node); } List<E> result = new ArrayList<>();for (E node : menuList) {//新增到下級資料中 setSubChildren.accept(node, parentMenuMap.getOrDefault(idGetter.apply(node), new ArrayList<>()));//如裡是根節點，加入結構if (rootCheck.test(node)) { result.add(node); } }return result;}

我們將設定獲取父級欄位方法，根節點的判定，獲取子列表方法都透過入參來指定，類實體透過泛型來整合，這樣不管面對任意屬性名稱或是特殊根級的值，都有很好的普適性。即拆即用，隨處可用，經過測試後泛型+函式式介面對效能幾乎沒有影響。

使用demo

publicstaticvoidmain(String[] args){// 生成10萬個測試資料 List<Menu> testMenus = generateTestMenus(100000);// 構建樹 List<Menu> tree = makeTree(testMenus, Menu::getParentId, Menu::getId, x -> x.getParentId() == 0, Menu::setSubMenus ); }

查詢樹search()方法

樹中查詢（當前節點不匹配predicate，只要其子節點列表匹配到即保留）

/** * 樹中查詢（當前節點不匹配predicate，只要其子節點列表匹配到即保留） * @param tree 需要查詢的樹 * @param predicate 過濾條件，根據業務場景自行修改 * @param getSubChildren 獲取下級資料方法，如：MenuVo::getSubMenus * @return List<E> 過濾後的樹 * @param <E> 泛型實體物件 */publicstatic <E> List<E> search(List<E> tree, Predicate<E> predicate, Function<E, List<E>> getSubChildren) { List<E> result = new ArrayList<>();for (E item : tree) { List<E> childList = getSubChildren.apply(item); List<E> filteredChildren = new ArrayList<>();if (childList != null && !childList.isEmpty()) { filteredChildren = search(childList, predicate, getSubChildren); }// 如果當前節點匹配，或者至少有一個子節點保留，就保留當前節點if (predicate.test(item) || !filteredChildren.isEmpty()) { result.add(item);// 還原下一級子節點如果有if (!filteredChildren.isEmpty()) { getSubChildren.apply(item).clear(); getSubChildren.apply(item).addAll(filteredChildren); } } }return result; }

如果當前節點未命中匹配條件，那麼繼續向下尋找，直到末級。

過濾樹filter()方法

filter()方法和Stream的filter()方法一樣，過濾滿足條件的資料節點，如裡當前節點不滿足其所有子節點都會過濾掉。

過濾樹

/** * 樹中過濾 * @param tree 需要進行過濾的樹 * @param predicate 過濾條件判斷 * @param getChildren 獲取下級資料方法，如：Menu::getSubMenus * @return List<E> 過濾後的樹 * @param <E> 泛型實體物件 */publicstatic <E> List<E> filter(List<E> tree, Predicate<E> predicate, Function<E, List<E>> getChildren) {return tree.stream().filter(item -> {if (predicate.test(item)) {List<E> children = getChildren.apply(item);if (children != null && !children.isEmpty()) { filter(children, predicate, getChildren); }returntrue; }returnfalse; }).collect(Collectors.toList()); }

使用demo

//查詢包含“ATA”選單的樹List<MenuVo> filterMenus =TreeUtil.filter(tree,x->x.getName()!=null&&x.contains("ATA");,MenuVo::getSubMenus);

排序 sort()方法

樹形結構進行排序

/** * 對樹形結構進行排序 * * @param tree 要排序的樹形結構，表示為節點列表。 * @param comparator 用於節點比較的比較器。 * @param getChildren 提供一種方法來獲取每個節點的子節點列表。 * @param <E> 元素的型別。 * @return 排序後的節點列表。 */publicstatic <E> List<E> sort(List<E> tree, Comparator<? super E> comparator, Function<E, List<E>> getChildren) {// 對樹的每個節點進行迭代處理for (E item : tree) {// 獲取當前節點的子節點列表List<E> childList = getChildren.apply(item);// 如果子節點列表不為空，則遞迴呼叫 sort 方法對其進行排序if (childList != null && !childList.isEmpty()) { sort(childList, comparator, getChildren); } }// 對當前層級的節點列表進行排序// 這一步確保了所有直接子節點在遞迴返回後都已排序，然後對當前列表進行排序 tree.sort(comparator);// 返回排序後的節點列表return tree; }

使用demo

// 定義比較器（比如按 ID 排序） Comparator<Menu> nodeComparator = Comparator.comparingInt(Menu::getId); List<Menu> sort = sort(tree, nodeComparator, Menu::getSubMenus);

過濾並處理 filterAndHandler()方法

橫向拓展，加入過濾或查詢條件，即可完成一個通用樹形過濾方法。再延伸，查詢到匹配的節點後對此節點進行特殊業務需求處理也是使用頻率極高的。

過濾並處理

/**

     * 樹中過濾並進行節點處理（此處是將節點的choose欄位置為false，那麼就在頁面上可以展示但無法被勾選）

* @param tree 需要過濾的樹 * @param predicate 過濾條件 * @param getChildren 獲取下級資料方法，如：MenuVo::getSubMenus * @param setChoose 要被處理的欄位，如：MenuVo::getChoose，可根據業務場景自行修改 * @param <E> 泛型實體物件 * @return List<E> 過濾後的樹 */

publicstatic <E> List<E> filterAndHandler(List<E> tree, Predicate<E> predicate, Function<E, List<E>> getChildren, BiConsumer<E, Boolean> setChoose) {

return tree.stream().filter(item -> {//如果命中條件，則可以被勾選。（可根據業務場景自行修改）if (predicate.test(item)) { setChoose.accept(item, true); } else { setChoose.accept(item, false); }List<E> children = getChildren.apply(item);if (children != null && !children.isEmpty()) { filterAndHandler(children, predicate, getChildren, setChoose); }returntrue; }).collect(Collectors.toList());}

上面展示的列表轉樹和查詢、搜尋、過濾、樹中過濾可任意合併為通用方法，以適配更多業務場景，減少重複程式碼，便於在其他系統中快速接入和使用。此外，該工具包還可擴充套件實現排序、前中後序遍歷等功能。

拓展：Traverser

Google 的開源庫 Guava[1] 提供了一些便捷的方法來處理樹形結構。事實上，其主要提供了對於圖結構的相關處理方法，同時可以相容樹、森林的處理。

Guava 的 Traverser 類是一個非常有用的工具，它可以處理樹形結構、圖的遍歷。透過使用這個類，你可以輕鬆實現各種樹的深度優先搜尋（DFS）、廣度優先搜尋（BFS）操作。雖然 Traverser 本身並不直接提供如修改、增刪節點等操作，因為其設計概念是基於不可變的結構遍歷，但可以透過合理的設計將這些功能整合在上層業務邏輯中。如果需要對結構本身進行修改、變形等操作，則需要編寫額外的邏輯來執行這些操作。

遍歷主要功能

1.不同方式的遍歷：

Pre-order Traversal（前序遍歷）：首先訪問節點本身，然後遞迴地訪問其子節點。
Post-order Traversal（後序遍歷）：遞迴地訪問節點的子節點，然後訪問節點本身。
Breadth-first Traversal（廣度優先遍歷）：按層級順序訪問節點，即從根節點開始逐層向下。

2.支援迴圈和圖形結構：

無向圖遍歷：Traverser 可以用於處理圖形結構的遍歷，透過配置可以避免重新訪問已訪問過的節點，從而避免在有迴圈的圖中陷入無限迴圈。
限定遍歷深度：在需要限制圖或樹遍歷的深度時，可以透過某些技巧來限制深度，這雖然需要一些DIY的實現，但Guava的構造提供了基礎支援。

拓展方法：遍歷樹

實際上，需要遍歷樹時，只需要指定父節點 => 子節點集合的對映方法即可。

遍歷樹demo

import com.alibaba.schedulerx.shade.com.google.common.collect.TreeTraverser;import com.fasterxml.jackson.core.JsonProcessingException;import com.fasterxml.jackson.databind.ObjectMapper;import java.util.ArrayList;import java.util.List;import java.util.function.Function;publicclassTreeUtilPro{privatestaticfinalObjectMapper objectMapper = new ObjectMapper();//遍歷策略（可根據使用者自己的使用場景設定）publicenumTraversalType{PRE_ORDER,POST_ORDER,BREADTH_FIRST }

publicstatic <T> String traverseTree(T root, Function<T, Iterable<T>> childrenFunction, TraversalType traversalType) throwsJsonProcessingException {

TreeTraverser<T> traverser = new TreeTraverser<T>() { @OverridepublicIterable<T> children(T node) {return childrenFunction.apply(node); } };List<T> nodes;// 根據遍歷型別選擇不同的遍歷策略switch (traversalType) {casePRE_ORDER: nodes = traverser.preOrderTraversal(root).toList();break;casePOST_ORDER: nodes = traverser.postOrderTraversal(root).toList();break;caseBREADTH_FIRST: nodes = traverser.breadthFirstTraversal(root).toList();break;default:throw new IllegalArgumentException("Unsupported traversal type"); }// Convert list of nodes to JSONreturn objectMapper.writeValueAsString(nodes); }}

使用demo

publicstaticvoidmain(String[] args) throws JsonProcessingException {// Example setup: Create a simple tree with menu Menu leaf1 = new Menu(1, "leaf1", 3, new ArrayList<>()); Menu leaf2 = new Menu(2, "leaf2", 3, new ArrayList<>()); Menu root = new Menu(3, "root", 4, Arrays.asList(leaf1, leaf2));// Example: Pre-order traversal String json = traverseTree(root, Menu::getSubMenus, TraversalType.PRE_ORDER); }

當然，也可以不用Guava裡面的方法，自己寫一個前中後序、深度或者廣度優先的方法，效果也是一樣的，這裡就不再贅述了。

執行效率

工具類中這些泛型和函式式介面的使用在對較深的樹封裝時會不會拖慢執行速度呢，我們還是使用5k，1w，5w和10w個節點來測試，並迴圈多次取平均值。

本地測試取平均值，不同機器、不同環境下可能會有不同的耗時時間（僅供參考）

我們可以從上圖看到，排除機器效能、軟體版本、時間計算方式等微小影響，兩者幾乎沒有效能上的差異。

總結

本文上述方法主要封裝了基礎的樹操作，工具類下的方法都使用了簡單健壯的泛型+函式式介面來接收入參和出參，不僅可以為單一專案中多個DO使用同時也能橫向對其他專案進行一樣的封裝並返回。工具類聚焦於構建和改造樹形的展示，而非直接對原始樹結構進行修改，例如節點的增刪或更新。這種設計源自不可變資料結構的遍歷思路，確保了操作的穩定性和減少副作用。

目前手頭的專案更多的涉及樹的子分支轉移或者更新、刪除。為了適應這些需要直接修改樹結構的需求，能夠實現動態變化節點或重構樹形的業務場景，正在考慮要不要實現封裝一些涉及資料庫變更的公共方法，能夠將指定的節點在資料層面實現變更，為系統提供更大的靈活性和功能擴充套件性，讓對樹結構處理的公共方法擴充套件到更多場景。