IT俱乐部 Java 详解Java递归实现树形结构的两种方式

详解Java递归实现树形结构的两种方式

发布: 2023年 4月 11日 218阅读

0、引言

在开发的过程中，很多业务场景需要一个树形结构的结果集进行前端展示，也可以理解为是一个无限父子结构，常见的有报表指标结构、菜单结构等。Java中递归实现树形结构的两种常见方式如下：

  • Java7及以下纯Java递归实现
  • Java8及以上借助lamda表达式实现

1、数据准备

Java实体类NodePO对应数据库表

package com.wbs.pojo;

import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.List;

@Data
@NoArgsConstructor
public class NodePO {

    /**
     * 当前节点id
     */
    private String id;

    /**
     * 当前节点名称
     */
    private String name;

    /**
     * 父级节点id
     */
    private String parentId;

    /**
     * 当前节点序号
     */
    private String orderNo;

    /**
     * 子集节点
     */
    private List children;

    /**
     * 构造函数
     * @param id
     * @param name
     * @param parentId
     * @param orderNo
     */
    public NodePO(String id,String name,String parentId,String orderNo){
        this.id = id;
        this.name = name;
        this.parentId = parentId;
        this.orderNo = orderNo;
    }
}

​ 自己造一些数据模拟从数据库中查询出来的数据：

static final List nodePOs = Arrays.asList(
            new NodePO("1","一级节点1",null,"_0001"),
            new NodePO("2","二级节点1.1","1","_0002"),
            new NodePO("3","二级节点1.2","1","_0003"),

            new NodePO("4","一级节点2",null,"_0004"),
            new NodePO("5","二级节点2.1","4","_0005"),
            new NodePO("6","二级节点2.2","4","_0006"),
            new NodePO("7","三级节点2.2.1","6","_0007"),

            new NodePO("8","一级节点3",null,"_0008"),
            new NodePO("9","二级节点3.1","8","_0009"),
            new NodePO("10","三级节点3.1.1","9","_0010"),
            new NodePO("11","四级节点3.1.1.1","10","_0011"),
            new NodePO("12","五级节点3.1.1.1.1","11","_0012")
    );

2、类型转化

从开发的过程中发现直接操作实体类集合，专门指定某一个实体类封装的方法是不具有普适性的，所以将实体类集合统一转化为Map集合，操作方便，具有一定的普适性：

List> mapList = BeanMapUtils.listBeanToListMap(jsonObject);

BeanMapUtils自己简单封装一个工具类（不惧普适性勿喷）：

package com.wbs.util;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import lombok.SneakyThrows;
import org.springframework.cglib.beans.BeanMap;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author 一宿君
 * @version Id: BeanMapUtils.java, v 0.1 Administrator Exp $$
 * @date 2022-10-13 14:24:20
 * @desc java实体类和map相互转换工具类
 */
public class BeanMapUtils {

    /**
     * 将实体类对象属性转化为map对象
     * @param t
     * @param 
     * @return
     */
    public static  Map beanToMap(T t) {
        Map map = new HashMap();
        if (t != null) {
            if (t instanceof JSONObject){
                return (JSONObject)t;
            }
            BeanMap beanMap = BeanMap.create(t);
            for (Object key : beanMap.keySet()) {
                map.put(key.toString(), beanMap.get(key));
            }
        }
        return map;
    }


    /**
     * 将map对象中转化为实体类对象
     * @param map
     * @param clazz
     * @param 
     * @return
     * @throws Exception
     */
    public static  T mapToBean(Map map,Class clazz) throws Exception {
        T bean = clazz.newInstance();
        if (bean instanceof JSONObject){
            JSONObject jsonObject = (JSONObject)bean;
            Set> entries = map.entrySet();
            for (Map.Entry entry : entries) {
                jsonObject.put(entry.getKey(),entry.getValue());
            }
            return (T)jsonObject;
        }
        BeanMap beanMap = BeanMap.create(bean);
        beanMap.putAll(map);
        return bean;
    }

    /**
     * 通过lambda表达式将List转化为List>
     * @param objList
     * @param 
     * @return
     */
    public static  List> listBeanToListMap(List objList) {
        return objList.stream().map(new Function>() {
            @Override
            public Map apply(T t) {
                Map map = Maps.newHashMap();
                if (t instanceof JSONObject){
                    return (JSONObject)t;
                }
                BeanMap beanMap = BeanMap.create(t);
                for (Object key : beanMap.keySet()) {
                    map.put(key.toString(), beanMap.get(key));
                }
                return map;
            }
        }).collect(Collectors.toList());
    }

    /**
     * 通过lambda表达式将List>转化为List
     * @param mapList
     * @param 
     * @return
     */
    public static  List listMapToListBean(List> mapList,Class clazz) {
        return mapList.stream().map(new Function,T>() {
            @SneakyThrows
            @Override
            public T apply(Map map) {
                T t = clazz.newInstance();
                if (t instanceof JSONObject){
                    return (T)map;
                }
                BeanMap beanMap = BeanMap.create(t);
                beanMap.putAll(map);
                return t;
            }
        }).collect(Collectors.toList());
    }
}

其中org.springframework.cglib.beans.BeanMap;是org.springframework:spring-core依赖下的工具包，spring-core核心依赖只要导入spring-boot-starter依赖即可

org.springframework.bootspring-boot-starter2.2.0.RELEASE

3、递归实现方法

3.1、Java7及以下纯Java递归实现

既然是Java7及以下实现方式，那排序也用最原始的冒泡排序：

/**
     * 冒泡排序,小的在前，大的在后
     * @param list
     * @return
     */
    public static List> sortJava7Map(List> list){
        if(CollectionUtils.isEmpty(list)){
            return Lists.newArrayList();
        }
        boolean flag;
        int size = list.size();
        for (int i = 0; i  frontMap = list.get(j - 1);
                Map afterMap = list.get(j);
                if (String.valueOf(frontMap.get("orderNo")).compareTo(String.valueOf(afterMap.get("orderNo"))) > 0){
                    list.set(j - 1,afterMap);
                    list.set(j,frontMap);
                    flag = true;
                }
            }
            //如果没有发生位置互换，则退出循环
            if (!flag){
                break;
            }
        }
        return list;
    }

给定一个节点，获取它的所有子节点：

/**
     * Java7及以下版本获取子节点的方式
     * @param parentNode
     * @param allList
     * @return
     */
    public static List> getJava7Children(Map parentNode,List> allList){

        //存放当前节点的直系子节点
        List> curNodeChildrenList = Lists.newArrayList();

        //存放直系子节点以外的节点
        List> otherNodeList = Lists.newArrayList();

        Object pId = parentNode.get("id");
        for (Map map : allList) {
            Object curPId = map.get("parentId");
            if (ObjectUtils.isNotEmpty(curPId) && Objects.equals(pId,curPId)){
                curNodeChildrenList.add(map);
            }else {
                otherNodeList.add(map);
            }
        }
        if (curNodeChildrenList.isEmpty()){
            return curNodeChildrenList;
        }
        //每一层级都进行排序
        curNodeChildrenList = sortJava7Map(curNodeChildrenList);

        //迭代直系子节点再获取子节点
        for (Map map : curNodeChildrenList) {
            map.put("children",getJava7Children(map,otherNodeList));
        }
        return curNodeChildrenList;
    }

给出一个结果集，构建树形结果集：

/**
     * 使用Java7的方式获取树形结构
     * @param allList
     * @return
     */
    public static List> getJava7ResultTree(List> allList){
        //存放所有的一级节点
        List> oneLevelNodeList = Lists.newArrayList();

        for (Map map : allList) {
            if (ObjectUtils.isEmpty(map.get("parentId"))){
                map.put("children",getJava7Children(map,allList));
                oneLevelNodeList.add(map);
            }
        }
        return sortJava8Map(oneLevelNodeList);
    }

获取树形结构：

//转化为Map集合
List> mapList = BeanMapUtils.listBeanToListMap(nodePOs);
//获取树形结构
List> java7ResultTree = getJava7ResultTree(mapList);
//打印输出
System.out.println(JSON.toJSONString(java7ResultTree));

打印结果：

[{“orderNo”:”_0001″,”children”:[{“orderNo”:”_0002″,”children”:[],”name”:”二级节点1.1″,”id”:”2″,”parentId”:”1″},{“orderNo”:”_0003″,”children”:[],”name”:”二级节点1.2″,”id”:”3″,”parentId”:”1″}],”name”:”一级节点1″,”id”:”1″},{“orderNo”:”_0004″,”children”:[{“orderNo”:”_0005″,”children”:[],”name”:”二级节点2.1″,”id”:”5″,”parentId”:”4″},{“orderNo”:”_0006″,”children”:[{“orderNo”:”_0007″,”children”:[],”name”:”三级节点2.2.1″,”id”:”7″,”parentId”:”6″}],”name”:”二级节点2.2″,”id”:”6″,”parentId”:”4″}],”name”:”一级节点2″,”id”:”4″},{“orderNo”:”_0008″,”children”:[{“orderNo”:”_0009″,”children”:[{“orderNo”:”_0010″,”children”:[{“orderNo”:”_0011″,”children”:[{“orderNo”:”_0012″,”children”:[],”name”:”五级节点3.1.1.1.1″,”id”:”12″,”parentId”:”11″}],”name”:”四级节点3.1.1.1″,”id”:”11″,”parentId”:”10″}],”name”:”三级节点3.1.1″,”id”:”10″,”parentId”:”9″}],”name”:”二级节点3.1″,”id”:”9″,”parentId”:”8″}],”name”:”一级节点3″,”id”:”8″}]

树形结构搞定！

3.2、Java8及以上借助lamda表达式实现

Java7的方式虽然实现了树形结构，但是有一定的缺点，比如：代码量比较大，逻辑相对较复杂，那Java8是如何简化，如下所示：

既然Java8有lamda表达式，那代码我们能省就省，先看排序，一行代码搞定：

/**
     * 根据orderNo排序树形结构的每一个层级
     * @param list
     * @return
     */
    public static List> sortJava8Map(List> list){
        if(CollectionUtils.isEmpty(list)){
            return Lists.newArrayList();
        }
        //关键之处，一行代码搞定
        list.sort(Comparator.comparing(m -> String.valueOf(m.get("orderNo"))));
        return list;
    }

给定一个节点，获取它的所有子节点：

释义：
filter： 过滤，相当于for循环，再if条件判断。
peek： 给定一个节点，往它的children塞子节点。

/**
     * 根据父级节点获取所有的子集节点
     * @param parentNode
     * @param allList
     * @return
     */
    public static List> getJava8Children(Map parentNode, List> allList){
        return allList.stream()
                .filter(curNode -> ObjectUtils.isNotEmpty(curNode.get("parentId")) && Objects.equals(curNode.get("parentId"),parentNode.get("id")))
                .peek(m -> m.put("children", getJava8Children(m,allList))).collect(Collectors.toList());
    }

给出一个结果集，构建树形结果集：

/**
     * 获取树形结构
     * @param mapList
     * @return treeList 树形结果集
     */
    public static List> getJava8ResultTree(List> mapList){
        if (CollectionUtils.isEmpty(mapList)){
            return Lists.newArrayList();
        }
        //filter过滤出所有的一级节点
        return mapList.stream().filter(m -> Objects.equals(m.get("parentId"), null) || Objects.equals(m.get("parentId"), ""))
                .peek(m -> m.put("children", sortJava8Map(getJava8Children(m, mapList)))).collect(Collectors.toList());
    }

获取树形结构：

//转化为Map集合
List> mapList = BeanMapUtils.listBeanToListMap(nodePOs);
//获取树形结构
List> java8ResultTree = getJava8ResultTree(mapList);
//打印输出
System.out.println(JSON.toJSONString(java8ResultTree));

打印结果：

[{“orderNo”:”_0001″,”children”:[{“orderNo”:”_0002″,”children”:[],”name”:”二级节点1.1″,”id”:”2″,”parentId”:”1″},{“orderNo”:”_0003″,”children”:[],”name”:”二级节点1.2″,”id”:”3″,”parentId”:”1″}],”name”:”一级节点1″,”id”:”1″},{“orderNo”:”_0004″,”children”:[{“orderNo”:”_0005″,”children”:[],”name”:”二级节点2.1″,”id”:”5″,”parentId”:”4″},{“orderNo”:”_0006″,”children”:[{“orderNo”:”_0007″,”children”:[],”name”:”三级节点2.2.1″,”id”:”7″,”parentId”:”6″}],”name”:”二级节点2.2″,”id”:”6″,”parentId”:”4″}],”name”:”一级节点2″,”id”:”4″},{“orderNo”:”_0008″,”children”:[{“orderNo”:”_0009″,”children”:[{“orderNo”:”_0010″,”children”:[{“orderNo”:”_0011″,”children”:[{“orderNo”:”_0012″,”children”:[],”name”:”五级节点3.1.1.1.1″,”id”:”12″,”parentId”:”11″}],”name”:”四级节点3.1.1.1″,”id”:”11″,”parentId”:”10″}],”name”:”三级节点3.1.1″,”id”:”10″,”parentId”:”9″}],”name”:”二级节点3.1″,”id”:”9″,”parentId”:”8″}],”name”:”一级节点3″,”id”:”8″}]

树形结构搞定！两种实现方式对比一下，你就说Java8的方式哇塞不哇塞！！！

到此这篇关于Java递归实现树形结构的两种方式的文章就介绍到这了,更多相关Java递归实现树形结构内容请搜索IT俱乐部以前的文章或继续浏览下面的相关文章希望大家以后多多支持IT俱乐部！

本文收集自网络，不代表IT俱乐部立场，转载请注明出处。https://www.2it.club/code/java/7084.html
20赞
标签:
上一篇
下一篇

相关推荐

联系我们

联系我们

在线咨询: QQ交谈

邮箱: 1120393934@qq.com

工作时间：周一至周五，9:00-17:30，节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部