列表结构与树结构转换分析与工具类封装(java版)

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
简介: 本文介绍了将线性列表转换为树形结构的实现方法及工具类封装。核心思路是先获取所有根节点,将其余节点作为子节点,通过递归构建每个根节点的子节点。关键在于节点需包含 `id`、`parentId` 和 `children` 三个属性。文中提供了两种封装方式:一是基于基类 `BaseTree` 的通用工具类,二是使用函数式接口实现更灵活的方式。推荐使用后者,因其避免了继承限制,更具扩展性。代码示例中使用了 Jackson 库进行 JSON 格式化输出,便于结果展示。最后总结指出,理解原理是进一步优化和封装的基础。

思路:

(1)先获取到所有根节点,把所有除根结点外的节点作为子节点,然后遍历每一个根节点,进行递归构建此根的子节点。

(2)递归时需要确定一个根节点,以及剩余子节点,如果子节点的父id等于根节点的id,那么就将这个节点加到根节点的children列表中,然后以当前节点作为根节点进行递归,检查是否还有子节点。

(3)关键:如何构建节点,这个节点中应该至少包含三个属性 idparentIdchildren

1、思路代码实现

【注意】代码中用到了jackson,你完全可以将其替换为fastjsongson,甚至不用,直接输出。

【注意】Node类中省略了getter与setter,请手动补齐,或用Lombok也可。

【注意】如果想直接拿到最终的封装好的工具类,直接看2.2

java

体验AI代码助手

代码解读

复制代码

import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;

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

public class ListToTree {

    public static List<Node> formatTree(List<Node> nodes) {
        List<Node> tree = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        // 1)先获取到所有根节点
        for (Node node : nodes) {
            if (node.getPid() == 0) {
                tree.add(node);
            } else {
                children.add(node);
            }
        }
        // 2)把所有除根结点外的节点作为子节点,然后遍历每一个根节点
        for (Node node : tree) {
            // 3)递归构建此根的子节点
            recur(node, children);
        }
        return tree;
    }

    public static void recur(Node rootNode, List<Node> children) {
        // 1)遍历剩余子节点,找出当前根的子节点
        for (Node node : children) {
            // 2)如果子节点的父id等于根节点的id,那么就将这个节点加到根节点的children列表中
            if (rootNode.getId() == node.getPid()) {
                if (rootNode.getChildren() == null) {
                    rootNode.setChildren(new ArrayList<>());
                }
                rootNode.getChildren().add(node);
                // 3)以当前节点作为根节点进行递归,检查是否还有子节点。
                recur(node, children);
            }
        }
    }

    public static void main(String[] args) throws JsonProcessingException {
        List<Node> nodes = Arrays.asList(
                new Node(1, 0, "类别1"),
                new Node(2, 0, "类别2"),
                new Node(3, 0, "类别3"),
                new Node(4, 1, "类别1-1"),
                new Node(5, 2, "类别2-1"),
                new Node(6, 1, "类别1-2"),
                new Node(7, 6, "类别1-2-1"));

        List<Node> tree = formatTree(nodes);

        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(tree));
    }
}

class Node {
    private String name;
    private int id;
    private int pid;
    private List<Node> children;

    public Node(int id, int pid, String name) {
        this.name = name;
        this.id = id;
        this.pid = pid;
    }

	// TODO: 省略getter 与 setter,请补全 

}

结果:

json

体验AI代码助手

代码解读

复制代码

[
    {
        "name": "节点1", 
        "id": 1, 
        "pid": 0, 
        "children": [
            {
                "name": "节点1-1", 
                "id": 4, 
                "pid": 1, 
                "children": null
            }, 
            {
                "name": "节点1-2", 
                "id": 6, 
                "pid": 1, 
                "children": [
                    {
                        "name": "节点1-2-1", 
                        "id": 7, 
                        "pid": 6, 
                        "children": null
                    }
                ]
            }
        ]
    }, 
    {
        "name": "节点2", 
        "id": 2, 
        "pid": 0, 
        "children": [
            {
                "name": "节点2-1", 
                "id": 5, 
                "pid": 2, 
                "children": null
            }
        ]
    }, 
    {
        "name": "节点3", 
        "id": 3, 
        "pid": 0, 
        "children": null
    }
]

2、工具类封装

2.1 封装基类实现

通过上面的代码可以发现,要构建树,idparentIdchildren这三个属性缺一不可,如果要让工具类通用,需要先封装一个基类,所有需要转换的实体需要继承此类,而工具代码的实现也基于这个类。

【注意】id不一定是Long,也可以是int,Integer等任意类型,只要比较即可。

java

体验AI代码助手

代码解读

复制代码

public class BaseTree {

    public Long id;

    public Long parentId;

    public List<BaseTree> children;

}

工具类代码:

java

体验AI代码助手

代码解读

复制代码

package cn.butcher.utils;

import cn.butcher.common.BaseTree;

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

/**
 * @author butcher
 * @description 列表-树 结构转换工具类
 */
public class ListAndTreeConverter {

    /**
     * <p> 列表转树,递归可以构建”无限“层次树 </p>
     * <p>
     * 使用时只需将待转换列表结构<code>List</code>传入,
     * 即可返回树结构<code>List</code>
     * </p>
     *
     * @param list 待转换列表
     * @param <T>  继承自BaseTree的实体
     * @return
     */
    public static <T extends BaseTree> List<T> formatTree(List<T> list) {
        List<T> tree = new ArrayList<>();
        List<T> children = new ArrayList<>();

        for (T node : list) {
            // 如果父节点为空,或者等于0,说明此节点为根节点,否则为子节点
            if (node.parentId == null || node.parentId == 0L) {
                tree.add(node);
            } else {
                children.add(node);
            }
        }

        // 分清顶级根节点后,构造每个根节点的子节点
        for (T rootNode : tree) {
            recur(rootNode, children);
        }
        return tree;
    }

    /**
     * <p> 树转列表,无视层级 </p>
     * <p>
     * 使用时只需将待转换树结构<code>List</code>传入,
     * 即可返回列表结构<code>List</code>
     * </p>
     *
     * @param tree 待转换树
     * @param <T>  继承自BaseTree的实体
     * @return 列表
     */
    public static <T extends BaseTree> List<T> formatList(List<T> tree) {
        List<T> list = new ArrayList<>();
        for (T node : tree) {
            list.add(node);
            recur(list, (List<T>) node.children);
            node.children = null;
        }
        // 根据id排序,此步可省
        Collections.sort(list, (a, b) -> (int) (a.id - b.id));
        return list;
    }

    private static <T extends BaseTree> void recur(T rootNode, List<T> children) {
        for (T node : children) {
            if (node.parentId.equals(rootNode.id)) {
                // 说明为此根的子节点
                if (rootNode.children == null) rootNode.children = new ArrayList<>();
                rootNode.children.add(node);
                recur(node, children);
            }
        }
    }

    private static <T extends BaseTree> void recur(List<T> list, List<T> children) {
        for (T node : children) {
            list.add(node);
            if (node.children != null && node.children.size() > 0) {
                recur(list, (List<T>) node.children);
                node.children = null;
            }
        }
    }
}

测试:

java

体验AI代码助手

代码解读

复制代码

package cn.butcher;

import cn.butcher.common.BaseTree;
import cn.butcher.utils.ListAndTreeConverter;
import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.Arrays;
import java.util.List;

public class TestList2Tree {

    public static void main(String[] args) throws JsonProcessingException {
        List<MyNode> nodes = Arrays.asList(
                new MyNode(1L, 0L, "节点1"),
                new MyNode(2L, 0L, "节点2"),
                new MyNode(3L, 1L, "节点1-1"),
                new MyNode(4L, 1L, "节点1-2"),
                new MyNode(5L, 2L, "节点2-1"),
                new MyNode(6L, 0L, "节点3"),
                new MyNode(7L, 3L, "节点1-1-1"));

        ObjectMapper mapper = new ObjectMapper();

        // 为转化之前
        System.out.println(mapper.writeValueAsString(nodes));

        // 列表转树
        nodes = ListAndTreeConverter.formatTree(nodes);
        System.out.println(mapper.writeValueAsString(nodes));

        // 树转列表
        nodes = ListAndTreeConverter.formatList(nodes);
        System.out.println(mapper.writeValueAsString(nodes));
    }
}

class MyNode extends BaseTree {
    // 本类私有属性
    private String name;

    public MyNode(Long id, Long pid, String name) {
        this.id = id;
        this.parentId = pid;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

结果:

json

体验AI代码助手

代码解读

复制代码

[
    {
        "id": 1, 
        "parentId": 0, 
        "children": [
            {
                "id": 3, 
                "parentId": 1, 
                "children": [
                    {
                        "id": 7, 
                        "parentId": 3, 
                        "children": null, 
                        "name": "节点1-1-1"
                    }
                ], 
                "name": "节点1-1"
            }, 
            {
                "id": 4, 
                "parentId": 1, 
                "children": null, 
                "name": "节点1-2"
            }
        ], 
        "name": "节点1"
    }, 
    {
        "id": 2, 
        "parentId": 0, 
        "children": [
            {
                "id": 5, 
                "parentId": 2, 
                "children": null, 
                "name": "节点2-1"
            }
        ], 
        "name": "节点2"
    }, 
    {
        "id": 6, 
        "parentId": 0, 
        "children": null, 
        "name": "节点3"
    }
]

2.2 使用函数式接口实现

对于上一种方式,你可能也发现了一些问题,就是还得写一个基类去让其他类继承,并且id、parentId都定死了,还是public的,入侵性太大!灵活性太低,假设在不同的场景下,对id要用不同的注解怎么办,public的属性名父子类不能重复。

所以为了解决上面的一些问题,可以使用函数式接口实现:

java

体验AI代码助手

代码解读

复制代码

package cn.butcher.utils;

import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.BiPredicate;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 * @author butcher
 * @date 2022/1/19 17:46
 * @description
 */
public class listAndTreeUtil {

    /**
     * 线性列表转树形列表
     *
     * @param source      数据源
     * @param checkRoot   如何判断是根节点,接收一个参数,当前节点
     * @param checkParent 如何判断是父节点,接收两个参数分别为根节点、当前节点
     * @param getChildren 如何拿到子节点列表
     * @param setChildren 如何设置子节点列表
     * @param <T>         节点类型
     * @return 树形列表
     */
    public static <T> List<T> formatTree(List<T> source, Predicate<T> checkRoot, BiPredicate<T, T> checkParent, Function<T, List<T>> getChildren, BiConsumer<T, List<T>> setChildren) {
        List<T> tree = new ArrayList<>();
        List<T> children = new ArrayList<>();
        for (T node : source) {
            if (checkRoot.test(node)) {
                tree.add(node);
            } else {
                children.add(node);
            }
        }
        for (T root : tree) {
            recur(root, children, checkParent, getChildren, setChildren);
        }
        return tree;
    }

    /**
     * 树形列表转线性列表
     *
     * @param source      数据源
     * @param getChildren 如何拿到子节点列表
     * @param setChildren 如何设置子节点列表
     * @param <T>         节点类型
     * @return 线性列表
     */
    public static <T> List<T> formatList(List<T> source, Function<T, List<T>> getChildren, BiConsumer<T, List<T>> setChildren) {
        List<T> list = new ArrayList<>();
        for (T node : source) {
            list.add(node);
            recur(list, getChildren.apply(node), getChildren, setChildren);
            setChildren.accept(node, null);
        }
        return list;
    }

    private static <T> void recur(T rootNode, List<T> children, BiPredicate<T, T> checkParent, Function<T, List<T>> getChildren, BiConsumer<T, List<T>> setChildren) {
        for (T node : children) {
            if (checkParent.test(rootNode, node)) {
                // 说明为此根的子节点
                List<T> list = getChildren.apply(rootNode);
                if (list == null) list = new ArrayList<>();
                list.add(node);
                setChildren.accept(rootNode, list);
                recur(node, children, checkParent, getChildren, setChildren);
            }
        }
    }

    private static <T> void recur(List<T> list, List<T> children, Function<T, List<T>> getChildren, BiConsumer<T, List<T>> setChildren) {
        if (children == null) return;
        for (T node : children) {
            list.add(node);
            List<T> c = getChildren.apply(node);
            if (c != null && c.size() > 0) {
                recur(list, c, getChildren, setChildren);
                setChildren.accept(node, null);
            }
        }
    }

    public static void main(String[] args) throws JsonProcessingException {
        List<AnyObj> anyObjs = Arrays.asList(
                AnyObj.builder().id(1).pid(0).build(),
                AnyObj.builder().id(2).pid(0).build(),
                AnyObj.builder().id(3).pid(1).build(),
                AnyObj.builder().id(4).pid(2).build(),
                AnyObj.builder().id(5).pid(3).build(),
                AnyObj.builder().id(6).pid(0).build()
        );

        ObjectMapper mapper = new ObjectMapper();

        System.out.println(mapper.writeValueAsString(anyObjs));

        List<AnyObj> formatTree = formatTree(anyObjs, o -> o.getPid() == 0, (r, n) -> r.getId() == n.getPid(), AnyObj::getChildren, AnyObj::setChildren);

        System.out.println(mapper.writeValueAsString(formatTree));

        List<AnyObj> formatList = formatList(formatTree, AnyObj::getChildren, AnyObj::setChildren);
        // 递归后的线性列表并不是有序的,如果对顺序有要求,可以
        Collections.sort(formatList, (a, b) -> a.getId() - b.getId());
        System.out.println(mapper.writeValueAsString(formatList));

    }
}

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
class AnyObj {
    private int id;
    private int pid;
    private List<AnyObj> children;
}

结果:

json

体验AI代码助手

代码解读

复制代码

[
    {
        "id": 1, 
        "pid": 0, 
        "children": [
            {
                "id": 3, 
                "pid": 1, 
                "children": [
                    {
                        "id": 5, 
                        "pid": 3, 
                        "children": null
                    }
                ]
            }
        ]
    }, 
    {
        "id": 2, 
        "pid": 0, 
        "children": [
            {
                "id": 4, 
                "pid": 2, 
                "children": null
            }
        ]
    }, 
    {
        "id": 6, 
        "pid": 0, 
        "children": null
    }
]

3、总结

线性列表转树形列表是我们开发中常见的问题,两种工具类的封装都是基于思路代码实现的,所以理解原理尤为重要,进一步封装也是基于原理来的。

并不推荐使用2.1的方式来实现通用工具类,它并不灵活,反而会给代码加上负担,2.2函数式接口的方式会是更好的选择,前提是你首先要了解java.util,function包下的这些接口。


转载来源:https://juejin.cn/post/7054441942549004319

目录
打赏
0
0
0
0
142
分享
相关文章
6个Java 工具,轻松分析定位 JVM 问题 !
本文介绍了如何使用 JDK 自带工具查看和分析 JVM 的运行情况。通过编写一段测试代码(启动 10 个死循环线程,分配大量内存),结合常用工具如 `jps`、`jinfo`、`jstat`、`jstack`、`jvisualvm` 和 `jcmd` 等,详细展示了 JVM 参数配置、内存使用、线程状态及 GC 情况的监控方法。同时指出了一些常见问题,例如参数设置错误导致的内存异常,并通过实例说明了如何排查和解决。最后附上了官方文档链接,方便进一步学习。
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
Java 中数组Array和列表List的转换
Java||Springboot读取本地目录的文件和文件结构,读取服务器文档目录数据供前端渲染的API实现
博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
Java||Springboot读取本地目录的文件和文件结构,读取服务器文档目录数据供前端渲染的API实现
|
22天前
|
Java 集合框架详解:系统化分析与高级应用
本文深入解析Java集合框架,涵盖List、Set、Map等核心接口及其常见实现类,如ArrayList、HashSet、HashMap等。通过对比不同集合类型的特性与应用场景,帮助开发者选择最优方案。同时介绍Iterator迭代机制、Collections工具类及Stream API等高级功能,提升代码效率与可维护性。适合初学者与进阶开发者系统学习与实践。
50 0
|
2月前
|
Java代码结构解析:类、方法、主函数(1分钟解剖室)
### Java代码结构简介 掌握Java代码结构如同拥有程序世界的建筑蓝图,类、方法和主函数构成“黄金三角”。类是独立的容器,承载成员变量和方法;方法实现特定功能,参数控制输入环境;主函数是程序入口。常见错误包括类名与文件名不匹配、忘记static修饰符和花括号未闭合。通过实战案例学习电商系统、游戏角色控制和物联网设备监控,理解类的作用、方法类型和主函数任务,避免典型错误,逐步提升编程能力。 **脑图速记法**:类如太空站,方法即舱段;main是发射台,static不能换;文件名对仗,括号要成双;参数是坐标,void不返航。
94 5
【JAVA】封装多线程原理
Java 中的多线程封装旨在简化使用、提高安全性和增强可维护性。通过抽象和隐藏底层细节,提供简洁接口。常见封装方式包括基于 Runnable 和 Callable 接口的任务封装,以及线程池的封装。Runnable 适用于无返回值任务,Callable 支持有返回值任务。线程池(如 ExecutorService)则用于管理和复用线程,减少性能开销。示例代码展示了如何实现这些封装,使多线程编程更加高效和安全。
Java网络编程封装
Java网络编程封装原理旨在隐藏底层通信细节,提供简洁、安全的高层接口。通过简化开发、提高安全性和增强可维护性,封装使开发者能更高效地进行网络应用开发。常见的封装层次包括套接字层(如Socket和ServerSocket类),以及更高层次的HTTP请求封装(如RestTemplate)。示例代码展示了如何使用RestTemplate简化HTTP请求的发送与处理,确保代码清晰易维护。
|
4月前
|
Java 面向对象编程的三大法宝:封装、继承与多态
本文介绍了Java面向对象编程中的三大核心概念:封装、继承和多态。
283 15
【潜意识Java】javaee中的SpringBoot在Java 开发中的应用与详细分析
本文介绍了 Spring Boot 的核心概念和使用场景,并通过一个实战项目演示了如何构建一个简单的 RESTful API。
82 5

数据库

+关注
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等