遞歸算法和樹狀結構的應用場景

一、遞歸算法

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、圖解和定義

它滿足:

n有一個特定的點稱為根節點(root)，n其余的節點分成n³0個獨立的集合T1, …, Tn，每個集合也都是一個樹狀結構。我們講T1, …, Tn為根節點的子樹(subtree)。

節點與邊:節點代表某項資料，而邊是指由一節點到另一節點的分支。

祖先(ancestor)節點與子孫(descendant)節點:如圖，A是所有節點的祖先，所有節點是A的子孫;而F是K與L的祖先，K與L是F的子孫。

父節點(parent node)與子節點(children node):如圖，B直接連到E與F且只差一個階度，則B為E與F的父節點，E與F為B的子節點。

兄弟節點(sibling node):擁有同一父節點的子節點。如:E與F。

葉節點(leaf node)或終點節點(terminal node):沒有子節點的節點。如:J、K等。

非葉節點(non-leaf node)或非終點節點(non-terminal node):有子節點的節點。 如:A、B、F等等。

根節點(root node):沒有父節點的節點，為樹的源頭。 如:A。

分支度(degree):指一個節點有幾個子節點。 如:A為3、B為2、C為1、M為0。

階度(level):為樹中的第幾代，而根節點為第一代，階度為1。

高度(height):指一節點往下走到葉節點的最長路徑。 如:A為3、F為1、L為0。

深度(depth):指從根節點到某一節點的最長路徑。如:C為1、M為3。

樹林(forest):由多個互斥樹(disjoint tree)所組成。 如圖將A移去便成為樹林。

三、應用場景

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)) ;
    }
}