詳解Java遞歸實現(xiàn)樹形結(jié)構(gòu)的兩種方式

更新時間：2022年10月24日 17:09:06 作者：一宿君

在開發(fā)的過程中，很多業(yè)務(wù)場景需要一個樹形結(jié)構(gòu)的結(jié)果集進行前端展示，也可以理解為是一個無限父子結(jié)構(gòu)，常見的有報表指標(biāo)結(jié)構(gòu)、菜單結(jié)構(gòu)等，這篇文章主要介紹了Java遞歸實現(xiàn)樹形結(jié)構(gòu)的兩種方式,需要的朋友可以參考下

0、引言

在開發(fā)的過程中，很多業(yè)務(wù)場景需要一個樹形結(jié)構(gòu)的結(jié)果集進行前端展示，也可以理解為是一個無限父子結(jié)構(gòu)，常見的有報表指標(biāo)結(jié)構(gòu)、菜單結(jié)構(gòu)等。Java中遞歸實現(xiàn)樹形結(jié)構(gòu)的兩種常見方式如下：

Java7及以下純Java遞歸實現(xiàn)
Java8及以上借助lamda表達式實現(xiàn)

1、數(shù)據(jù)準(zhǔn)備

Java實體類NodePO對應(yīng)數(shù)據(jù)庫表

package com.wbs.pojo;

import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.List;

@Data
@NoArgsConstructor
public class NodePO {

    /**
     * 當(dāng)前節(jié)點id
     */
    private String id;

    /**
     * 當(dāng)前節(jié)點名稱
     */
    private String name;

    /**
     * 父級節(jié)點id
     */
    private String parentId;

    /**
     * 當(dāng)前節(jié)點序號
     */
    private String orderNo;

    /**
     * 子集節(jié)點
     */
    private List<NodePO> children;

    /**
     * 構(gòu)造函數(shù)
     * @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;
    }
}

? 自己造一些數(shù)據(jù)模擬從數(shù)據(jù)庫中查詢出來的數(shù)據(jù)：

static final List<NodePO> nodePOs = Arrays.asList(
            new NodePO("1","一級節(jié)點1",null,"_0001"),
            new NodePO("2","二級節(jié)點1.1","1","_0002"),
            new NodePO("3","二級節(jié)點1.2","1","_0003"),

            new NodePO("4","一級節(jié)點2",null,"_0004"),
            new NodePO("5","二級節(jié)點2.1","4","_0005"),
            new NodePO("6","二級節(jié)點2.2","4","_0006"),
            new NodePO("7","三級節(jié)點2.2.1","6","_0007"),

            new NodePO("8","一級節(jié)點3",null,"_0008"),
            new NodePO("9","二級節(jié)點3.1","8","_0009"),
            new NodePO("10","三級節(jié)點3.1.1","9","_0010"),
            new NodePO("11","四級節(jié)點3.1.1.1","10","_0011"),
            new NodePO("12","五級節(jié)點3.1.1.1.1","11","_0012")
    );

2、類型轉(zhuǎn)化

從開發(fā)的過程中發(fā)現(xiàn)直接操作實體類集合，專門指定某一個實體類封裝的方法是不具有普適性的，所以將實體類集合統(tǒng)一轉(zhuǎn)化為Map集合，操作方便，具有一定的普適性：

List<Map<String, Object>> 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相互轉(zhuǎn)換工具類
 */
public class BeanMapUtils {

    /**
     * 將實體類對象屬性轉(zhuǎn)化為map對象
     * @param t
     * @param <T>
     * @return
     */
    public static <T> Map<String, Object> beanToMap(T t) {
        Map<String, Object> 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對象中轉(zhuǎn)化為實體類對象
     * @param map
     * @param clazz
     * @param <T>
     * @return
     * @throws Exception
     */
    public static <T> T mapToBean(Map<String, Object> map,Class<T> clazz) throws Exception {
        T bean = clazz.newInstance();
        if (bean instanceof JSONObject){
            JSONObject jsonObject = (JSONObject)bean;
            Set<Map.Entry<String, Object>> entries = map.entrySet();
            for (Map.Entry<String, Object> entry : entries) {
                jsonObject.put(entry.getKey(),entry.getValue());
            }
            return (T)jsonObject;
        }
        BeanMap beanMap = BeanMap.create(bean);
        beanMap.putAll(map);
        return bean;
    }

    /**
     * 通過lambda表達式將List<JavaBean>轉(zhuǎn)化為List<Map<String, Object>>
     * @param objList
     * @param <T>
     * @return
     */
    public static <T> List<Map<String, Object>> listBeanToListMap(List<T> objList) {
        return objList.stream().map(new Function<T, Map<String, Object>>() {
            @Override
            public Map<String, Object> apply(T t) {
                Map<String,Object> 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<Map<String, Object>>轉(zhuǎn)化為List<JavaBean>
     * @param mapList
     * @param <T>
     * @return
     */
    public static <T> List<T> listMapToListBean(List<Map<String,Object>> mapList,Class<T> clazz) {
        return mapList.stream().map(new Function<Map<String, Object>,T>() {
            @SneakyThrows
            @Override
            public T apply(Map<String, Object> 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核心依賴只要導(dǎo)入spring-boot-starter依賴即可

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter</artifactId>
    <version>2.2.0.RELEASE</version>
</dependency>

在這里插入圖片描述

3、遞歸實現(xiàn)方法

3.1、Java7及以下純Java遞歸實現(xiàn)

既然是Java7及以下實現(xiàn)方式，那排序也用最原始的冒泡排序：

/**
     * 冒泡排序,小的在前，大的在后
     * @param list
     * @return
     */
    public static List<Map<String, Object>> sortJava7Map(List<Map<String, Object>> list){
        if(CollectionUtils.isEmpty(list)){
            return Lists.newArrayList();
        }
        boolean flag;
        int size = list.size();
        for (int i = 0; i < size - 1; i++) {
            flag = false;
            for (int j = 1; j < size - i; j++) {
                Map<String, Object> frontMap = list.get(j - 1);
                Map<String, Object> 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;
                }
            }
            //如果沒有發(fā)生位置互換，則退出循環(huán)
            if (!flag){
                break;
            }
        }
        return list;
    }

給定一個節(jié)點，獲取它的所有子節(jié)點：

/**
     * Java7及以下版本獲取子節(jié)點的方式
     * @param parentNode
     * @param allList
     * @return
     */
    public static List<Map<String, Object>> getJava7Children(Map<String,Object> parentNode,List<Map<String, Object>> allList){

        //存放當(dāng)前節(jié)點的直系子節(jié)點
        List<Map<String, Object>> curNodeChildrenList = Lists.newArrayList();

        //存放直系子節(jié)點以外的節(jié)點
        List<Map<String, Object>> otherNodeList = Lists.newArrayList();

        Object pId = parentNode.get("id");
        for (Map<String, Object> 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);

        //迭代直系子節(jié)點再獲取子節(jié)點
        for (Map<String, Object> map : curNodeChildrenList) {
            map.put("children",getJava7Children(map,otherNodeList));
        }
        return curNodeChildrenList;
    }

給出一個結(jié)果集，構(gòu)建樹形結(jié)果集：

/**
     * 使用Java7的方式獲取樹形結(jié)構(gòu)
     * @param allList
     * @return
     */
    public static List<Map<String, Object>> getJava7ResultTree(List<Map<String, Object>> allList){
        //存放所有的一級節(jié)點
        List<Map<String, Object>> oneLevelNodeList = Lists.newArrayList();

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

獲取樹形結(jié)構(gòu)：

//轉(zhuǎn)化為Map集合
List<Map<String, Object>> mapList = BeanMapUtils.listBeanToListMap(nodePOs);
//獲取樹形結(jié)構(gòu)
List<Map<String, Object>> java7ResultTree = getJava7ResultTree(mapList);
//打印輸出
System.out.println(JSON.toJSONString(java7ResultTree));

打印結(jié)果：

[{"orderNo":"_0001","children":[{"orderNo":"_0002","children":[],"name":"二級節(jié)點1.1","id":"2","parentId":"1"},{"orderNo":"_0003","children":[],"name":"二級節(jié)點1.2","id":"3","parentId":"1"}],"name":"一級節(jié)點1","id":"1"},{"orderNo":"_0004","children":[{"orderNo":"_0005","children":[],"name":"二級節(jié)點2.1","id":"5","parentId":"4"},{"orderNo":"_0006","children":[{"orderNo":"_0007","children":[],"name":"三級節(jié)點2.2.1","id":"7","parentId":"6"}],"name":"二級節(jié)點2.2","id":"6","parentId":"4"}],"name":"一級節(jié)點2","id":"4"},{"orderNo":"_0008","children":[{"orderNo":"_0009","children":[{"orderNo":"_0010","children":[{"orderNo":"_0011","children":[{"orderNo":"_0012","children":[],"name":"五級節(jié)點3.1.1.1.1","id":"12","parentId":"11"}],"name":"四級節(jié)點3.1.1.1","id":"11","parentId":"10"}],"name":"三級節(jié)點3.1.1","id":"10","parentId":"9"}],"name":"二級節(jié)點3.1","id":"9","parentId":"8"}],"name":"一級節(jié)點3","id":"8"}]

樹形結(jié)構(gòu)搞定！

3.2、Java8及以上借助lamda表達式實現(xiàn)

Java7的方式雖然實現(xiàn)了樹形結(jié)構(gòu)，但是有一定的缺點，比如：代碼量比較大，邏輯相對較復(fù)雜，那Java8是如何簡化，如下所示：

既然Java8有l(wèi)amda表達式，那代碼我們能省就省，先看排序，一行代碼搞定：

/**
     * 根據(jù)orderNo排序樹形結(jié)構(gòu)的每一個層級
     * @param list
     * @return
     */
    public static List<Map<String, Object>> sortJava8Map(List<Map<String, Object>> list){
        if(CollectionUtils.isEmpty(list)){
            return Lists.newArrayList();
        }
        //關(guān)鍵之處，一行代碼搞定
        list.sort(Comparator.comparing(m -> String.valueOf(m.get("orderNo"))));
        return list;
    }

給定一個節(jié)點，獲取它的所有子節(jié)點：

釋義：
filter： 過濾，相當(dāng)于for循環(huán)，再if條件判斷。
peek： 給定一個節(jié)點，往它的children塞子節(jié)點。

/**
     * 根據(jù)父級節(jié)點獲取所有的子集節(jié)點
     * @param parentNode
     * @param allList
     * @return
     */
    public static List<Map<String, Object>> getJava8Children(Map<String,Object> parentNode, List<Map<String, Object>> 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());
    }

給出一個結(jié)果集，構(gòu)建樹形結(jié)果集：

/**
     * 獲取樹形結(jié)構(gòu)
     * @param mapList
     * @return treeList 樹形結(jié)果集
     */
    public static List<Map<String, Object>> getJava8ResultTree(List<Map<String, Object>> mapList){
        if (CollectionUtils.isEmpty(mapList)){
            return Lists.newArrayList();
        }
        //filter過濾出所有的一級節(jié)點
        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());
    }

獲取樹形結(jié)構(gòu)：

//轉(zhuǎn)化為Map集合
List<Map<String, Object>> mapList = BeanMapUtils.listBeanToListMap(nodePOs);
//獲取樹形結(jié)構(gòu)
List<Map<String, Object>> java8ResultTree = getJava8ResultTree(mapList);
//打印輸出
System.out.println(JSON.toJSONString(java8ResultTree));

打印結(jié)果：

[{"orderNo":"_0001","children":[{"orderNo":"_0002","children":[],"name":"二級節(jié)點1.1","id":"2","parentId":"1"},{"orderNo":"_0003","children":[],"name":"二級節(jié)點1.2","id":"3","parentId":"1"}],"name":"一級節(jié)點1","id":"1"},{"orderNo":"_0004","children":[{"orderNo":"_0005","children":[],"name":"二級節(jié)點2.1","id":"5","parentId":"4"},{"orderNo":"_0006","children":[{"orderNo":"_0007","children":[],"name":"三級節(jié)點2.2.1","id":"7","parentId":"6"}],"name":"二級節(jié)點2.2","id":"6","parentId":"4"}],"name":"一級節(jié)點2","id":"4"},{"orderNo":"_0008","children":[{"orderNo":"_0009","children":[{"orderNo":"_0010","children":[{"orderNo":"_0011","children":[{"orderNo":"_0012","children":[],"name":"五級節(jié)點3.1.1.1.1","id":"12","parentId":"11"}],"name":"四級節(jié)點3.1.1.1","id":"11","parentId":"10"}],"name":"三級節(jié)點3.1.1","id":"10","parentId":"9"}],"name":"二級節(jié)點3.1","id":"9","parentId":"8"}],"name":"一級節(jié)點3","id":"8"}]

樹形結(jié)構(gòu)搞定！兩種實現(xiàn)方式對比一下，你就說Java8的方式哇塞不哇塞?。?！

到此這篇關(guān)于Java遞歸實現(xiàn)樹形結(jié)構(gòu)的兩種方式的文章就介紹到這了,更多相關(guān)Java遞歸實現(xiàn)樹形結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: