递归算法和树状结构的应用场景

一、递归算法

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