基于遞歸算法，樹形結構資料下業務場景，封裝解決方法

本文源碼： GitHub·點這裡 || GitEE·點這裡

一、遞歸算法

1、概念簡介

遞歸算法的核心思想是通過将問題重複分解為同類的或其子問題的方式，進而可以使用統一的解決方式。很多程式設計語言支援方法或函數自我調用，簡單的說，就是在函數或方法體内，自身可以再次調用自身的方法結構。

2、基礎案例

這裡通過遞歸的方式，計算階乘、求和等相關邏輯。

public class Demo01 {
    public static void main(String[] args) {
        int result1 = factorial(5);
        System.out.println(result1);
        int result2 = sum(100) ;
        System.out.println(result2);
    }
    // 遞歸階乘
    private static int factorial (int n){
        if(n <= 1){
            return n ;
        }else{
            return n*factorial(n-1);
        }
    }
    // 遞歸求和
    private static int sum (int f){
        if(f <= 1){
            return f ;
        }else{
            return f + sum(f-1);
        }
    }
}           

3、注意事項

• 使用方法

使用遞歸的時候，要明确業務邏輯可以分解為重複相同的問題，且要清楚的知道遞歸的結束條件，不然很容易出現死循環。

• 優缺點描述

遞歸算法的代碼比較簡潔，可讀性較好；但是在實際的業務進行中會出現多次的重複調用，如果處理不好，很容易出現StackOverflowError報錯。

二、樹狀結構

1、概念描述

樹形結構是一層次的嵌套結構。一個樹形結構的外層和内層有相似的結構，是以這種結構多可以遞歸的表示。

2、圖解和定義

• 根節點

樹的根源，沒有父節點的節點，如上圖A節點。

• 兄弟節點

擁有同一父節點的子節點。如圖B與C與D節點。

• 葉子節點

沒有子節點的節點。如圖E和F等節點。

• 分支度

指一個節點有幾個子節點。 如：A為3、B為2。

• 節點深度

指從該節點到某一節點的最長路徑。如圖A為2、B為1。

三、應用場景

1、場景描述

基于遞歸算法下，處理很多樹形結構的業務資料。常見的業務場景如下：

• 省市區三級關聯查詢 ；
• 系統子產品、菜單、按鈕的授權 ；
• 常見的業務資料分類：商品分類等 ；
• 常見各種行業分類細化 ；

2、特殊場景

在管理系統中，對系統子產品、菜單、按鈕授權操作時候可能會出現如下情況。

假如系統管理者的權限如圖所示，但是給到營運人員的權限如下，需要把3号菜單和5号菜單設定為同級别，這時候基本的處理手法就是把3号菜單父級ID作為3号菜單和下屬功能的權限的根節點，這裡把這裡當成兩顆樹進行分别處理，最後合并資料就好。必要時按照配上節點編碼，例如NODE01,NODE0101,NODE0102等方式，這裡針對這個場景描述，就是希望在處理類似業務時候，思路要開闊，不必拘泥于單個樹形結構。

業務很多時候都是出人意料甚至是令人生厭，不過這确實就是生活

。

3、工具類封裝

這裡展示一個樹形結構常用的幾個封裝方法，例如建立樹形結構，周遊，判斷等。

import java.util.ArrayList;
import java.util.List;

public class ThreeUtil {
    /**
     * 遞歸建立樹形結構
     */
    private static List<ThreeNode> getTree(List<ThreeNode> nodeList, Integer parentId) {
        List<ThreeNode> threeNodeList = new ArrayList<>() ;
        for (ThreeNode entity : nodeList) {
            Integer nodeId = entity.getId() ;
            Integer nodeParentId = entity.getParentId() ;
            if (parentId.intValue() == nodeParentId.intValue()) {
                List<ThreeNode> childList = getTree(nodeList,nodeId) ;
                if (childList != null && childList.size()>0){
                    entity.setChildNode(childList);
                    entity.setChildNodeSize(childList.size());
                }
                threeNodeList.add(entity) ;
            }
        }
        return threeNodeList ;
    }

    /**
     * 擷取指定子節點
     */
    private static List<ThreeNode> getChildTree (Integer id,List<ThreeNode> nodeList){
        List<ThreeNode> resultList = new ArrayList<>();
        for (ThreeNode entity : nodeList) {
            if (entity.getParentId().intValue() == id) {
                List<ThreeNode> childList = getChildTree(entity.getId(),nodeList) ;
                entity.setChildNode(childList);
                entity.setChildNodeSize(childList.size());
                resultList.add(entity) ;
            }
        }
        return resultList ;
    }

    /**
     * 周遊樹形結構
     */
    private static transient List<Integer> treeIdList = new ArrayList<>() ;
    private static List<Integer> getTreeInfo (List<ThreeNode> treeList){
        for (ThreeNode entity : treeList) {
            if (entity.getChildNodeSize()!=null && entity.getChildNodeSize()>0){
                getTreeInfo(entity.getChildNode());
            }
            treeIdList.add(entity.getId());
        }
        return treeIdList ;
    }

    /**
     * 判斷節是否是葉子節點
     */
    private static boolean hasChildNode (Integer id,List<ThreeNode> nodeList){
        for (ThreeNode entity:nodeList){
            if (entity.getParentId().intValue() == id){
                return true ;
            }
        }
        return false ;
    }

    public static void main(String[] args) {
        List<ThreeNode> threeNodeList = new ArrayList<>() ;
        threeNodeList.add(new ThreeNode(1,"節點A",0)) ;
        threeNodeList.add(new ThreeNode(2,"節點B",1)) ;
        threeNodeList.add(new ThreeNode(3,"節點C",1)) ;
        threeNodeList.add(new ThreeNode(4,"節點D",1)) ;
        threeNodeList.add(new ThreeNode(5,"節點E",2)) ;
        threeNodeList.add(new ThreeNode(6,"節點F",2)) ;
        // 測試1
        List<ThreeNode> getTree = getTree(threeNodeList,0) ;
        System.out.println(getTree);
        // 測試2
        // List<ThreeNode> getChildTree = getChildTree(2,threeNodeList) ;
        // System.out.println(getChildTree);
        // 測試3
        List<Integer> treeIdList = getTreeInfo(getTree) ;
        System.out.println(treeIdList);
        // 測試4
        System.out.println(hasChildNode(2,threeNodeList)) ;
    }
}           

四、源代碼位址

GitHub·位址
https://github.com/cicadasmile
GitEE·位址
https://gitee.com/cicadasmile