温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2020-06-11 18:33:47 来源:亿速云 阅读:338 作者:元一 栏目:编程语言

一、递归算法

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&sup3;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)) ;
        }
    }
    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    AI