遞歸算法和樹狀結(jié)構(gòu)的應(yīng)用場景

一、遞歸算法

1、概念簡介

遞歸算法是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。一個(gè)過程(或函數(shù))直接或間接調(diào)用自己本身,這種過程(或函數(shù))叫遞歸過程(或函數(shù))。

2、基礎(chǔ)案例

這里通過遞歸的方式，計(jì)算階乘、求和等相關(guān)邏輯。

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、注意事項(xiàng)

• 使用方法

使用遞歸的時(shí)候，要明確業(yè)務(wù)邏輯可以分解為重復(fù)相同的問題，且要清楚的知道遞歸的結(jié)束條件，不然很容易出現(xiàn)死循環(huán)。

• 優(yōu)缺點(diǎn)描述

遞歸算法的代碼比較簡潔，可讀性較好；但是在實(shí)際的業(yè)務(wù)處理中會出現(xiàn)多次的重復(fù)調(diào)用，如果處理不好，很容易出現(xiàn)StackOverflowError報(bào)錯(cuò)。

二、樹狀結(jié)構(gòu)

1、概念描述

樹狀結(jié)構(gòu)是一個(gè)或多個(gè)節(jié)點(diǎn)的有限集合。

2、圖解和定義

它滿足:

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

節(jié)點(diǎn)與邊:節(jié)點(diǎn)代表某項(xiàng)資料，而邊是指由一節(jié)點(diǎn)到另一節(jié)點(diǎn)的分支。

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

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

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

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

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

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

分支度(degree):指一個(gè)節(jié)點(diǎn)有幾個(gè)子節(jié)點(diǎn)。 如:A為3、B為2、C為1、M為0。

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

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

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

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

三、應(yīng)用場景

1、場景描述

基于遞歸算法下，處理很多樹形結(jié)構(gòu)的業(yè)務(wù)數(shù)據(jù)。常見的業(yè)務(wù)場景如下：

• 省市區(qū)三級聯(lián)動(dòng)查詢 ；
• 系統(tǒng)模塊、菜單、按鈕的授權(quán) ；
• 常見的業(yè)務(wù)數(shù)據(jù)分類：商品分類等 ；
• 常見各種行業(yè)分類細(xì)化 ；

2、特殊場景

在管理系統(tǒng)中，對系統(tǒng)模塊、菜單、按鈕授權(quán)操作時(shí)候可能會出現(xiàn)如下情況。

假如系統(tǒng)管理員的權(quán)限如圖所示，但是給到運(yùn)營人員的權(quán)限如下，需要把3號菜單和5號菜單設(shè)置為同級別，這時(shí)候基本的處理手法就是把3號菜單父級ID作為3號菜單和下屬功能的權(quán)限的根節(jié)點(diǎn)，這里把這里當(dāng)成兩顆樹進(jìn)行分別處理，最后合并數(shù)據(jù)就好。必要時(shí)按照配上節(jié)點(diǎn)編碼，例如NODE01,NODE0101,NODE0102等方式，這里針對這個(gè)場景描述，就是希望在處理類似業(yè)務(wù)時(shí)候，思路要開闊，不必拘泥于單個(gè)樹形結(jié)構(gòu)。業(yè)務(wù)很多時(shí)候都是出人意料甚至是令人生厭，不過這確實(shí)就是生活。

3、工具類封裝

這里展示一個(gè)樹形結(jié)構(gòu)常用的幾個(gè)封裝方法，例如創(chuàng)建樹形結(jié)構(gòu)，遍歷，判斷等。

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

public class ThreeUtil {
    /**
     * 遞歸創(chuàng)建樹形結(jié)構(gòu)
     */
    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 ;
    }

    /**
     * 獲取指定子節(jié)點(diǎn)
     */
    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 ;
    }

    /**
     * 遍歷樹形結(jié)構(gòu)
     */
    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 ;
    }

    /**
     * 判斷節(jié)是否是葉子節(jié)點(diǎn)
     */
    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,"節(jié)點(diǎn)A",0)) ;
        threeNodeList.add(new ThreeNode(2,"節(jié)點(diǎn)B",1)) ;
        threeNodeList.add(new ThreeNode(3,"節(jié)點(diǎn)C",1)) ;
        threeNodeList.add(new ThreeNode(4,"節(jié)點(diǎn)D",1)) ;
        threeNodeList.add(new ThreeNode(5,"節(jié)點(diǎn)E",2)) ;
        threeNodeList.add(new ThreeNode(6,"節(jié)點(diǎn)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)) ;
    }
}