Java实现平铺列表(List)互转树形(Tree)结构

目录
  • 需求
  • 实践List to Tree
    • 递归实现
    • 非递归实现
    • 实例
  • 实践Tree to List
    • 递归实现
    • 非递归实现
    • 实例
  • 总结

很多时候为满足前后端交互的数据结构需求,往往我们需要把平铺的List数据与Tree型层级数据结构进行互转,这篇文章提供详实的递归和非递归的方式去实现数据结构转换,为了使用到lambda的特性,Java version >=8

需求

我们从基础设施层获取了一个列表数据,列表其中的对象结构如下,注意约束条件如果没有pid,默认为null

@Getter
@Setter
@ToString
@Builder
public class NodeEntity {

    /**
     * id
     */
    private Long id;

    /**
     * 父id
     */
    private Long pid;
}

现在我们要将List<NodeEntity> 数据,按照属性pid进行Tree型层级封装,并且支持多层级封装。一般很容易想到递归的实现方法,接下来这篇文章使用一套通用的解决办法,非递归实现结构转换。

实践List to Tree

递归实现

首先定义通用的Tree形数据接口。

public interface INodeDTO {

    /**
     * id
     * @return id
     */
    public Long getId();

    /**
     * pid
     * @return  pid
     */
    public Long getPid();

    /**
     * 获取Children
     * @return  Children
     */
    public List<INodeDTO> getChildren();

    /**
     * 设置children
     * @param children  children
     */
    public void setChildren(List<INodeDTO> children);

}

每个方法接口有详细的注释,无需多说。然后提供通用的转换Function

/**
     * 非递归实现平铺数据转成Tree型结构
     */
    static final Function<List<INodeDTO>,List<INodeDTO>> MULTI_TREE_CONVERTER = sources->
        sources.stream()
            .filter(item->{
                item.setChildren(
                    sources.stream()
                        .filter(e-> Objects.equals(e.getPid(), item.getId()))
                        .collect(Collectors.toList()));
                return item.getPid() == null;})
            .collect(Collectors.toList());

我们利用对象引用,浅拷贝的原理,通过循环查找来组装层级,最后根据pid==null的数据一定是Tree型第一层的数据的条件进行过滤,筛选出第一层的数据组合成新的列表,达到目的。

非递归实现

//Establish tree structure
static List<INodeDTO> buildTree (List<INodeDTO>sources){
    List<INodeDTO> results = new ArrayList<>();
    //get root nodes
    List<INodeDTO> rootNodes = sources.stream().filter(x->x.getPid() == null).collect(Collectors.toList());
    for (INodeDTO rootNode : rootNodes) {
        results.add(buildChildTree(sources,rootNode));
    }
    return results;
}

//Recursion, building subtree structure
static INodeDTO buildChildTree(List<INodeDTO>sources,INodeDTO pNode){
    List<INodeDTO> children = new ArrayList<>();
    for (INodeDTO source : sources) {
        if(source.getPid()!=null && source.getPid().equals(pNode.getId())){
            children.add(buildChildTree(sources,source));
        }
    }
    pNode.setChildren(children);
    return pNode;
}

递归的实现先获取所有根节点,方法builTree总结根节点来创建一个树结构,buildChilTree为节点构建一个辅助树,并拼接当前树,递归调用buildChilTree来不断打开当前树的分支和叶子,直到没有找到新的子树, 完成递归,得到树结构。

递归最大的问题可能堆栈太深,容易造成溢出,使用需要谨慎,而且从代码简洁度来说,肯定是使用了非递归的方式更好。

递归代码还能进一步优化,比如改成尾递归的方式,有兴趣的小伙伴可以尝试一下。

实例

实例只测试非递归实现方法。

那具体怎么使用呢?首先我们通过implements接口INodeDTO,实现我们自己的业务DTO

@Getter
@Setter
@ToString
@Builder
public class NodeDTO implements INodeDTO {

    private Long id;

    private Long pid;

    List<INodeDTO> children;
}

然后在我们Service层组装业务逻辑,这里提供一个listBy的条件查询接口,从基础设施层按照条件捞出List<NodeEntity>,期望转成内部包含层级关系的List<INodeDTO>

public class UseCase {

    public List<INodeDTO> listBy(String ... condtions){
        System.out.println(Arrays.stream(condtions).reduce((a, b) -> a + ";" + b).orElse(""));
        //TODO get NodeEntities from database
        List<NodeEntity> entities = Arrays.asList(
                NodeEntity.builder().id(1L).pid(null).build(),
                NodeEntity.builder().id(2L).pid(1L).build(),
                NodeEntity.builder().id(3L).pid(1L).build(),
                NodeEntity.builder().id(4L).pid(3L).build()
            );
        List<INodeDTO> sources = entities.stream()
            .map(Factory.NODE_DTO_BUILDER::apply)
            .collect(Collectors.toList());
        return INodeDTO.MULTI_TREE_CONVERTER.apply(sources);
    }

}

提供一个main方法进行测试。

public static void main(String[] args) throws JsonProcessingException {
        UseCase useCase = new UseCase();
        List<INodeDTO> results = useCase.listBy("condtion1", "condtion2");
        //convert json with style
        ObjectMapper objectMapper = new ObjectMapper();
        String json = objectMapper.writerWithDefaultPrettyPrinter().writeValueAsString(results);
        System.out.println(json);
    }

运行后输出结果如下,经人工肉眼检验,达到Tree型层级结构。

实践Tree to List

上面讲到了平铺列表(List)转树形(Tree)结构,一般来说对于足够后端数据转成前端想要的结构了。但都支持了正向转换,那么反向转换,即树形(Tree)结构如何转平铺列表(List)呢?

递归实现

递归实现,分为两个函数,List<INodeDTO> flatten(List<INodeDTO> flatList) 接受外部调用,传入待转换的Tree形结构。第一步便是收集所有的根节点,然后将所有的根节点传入到递归函数List<INodeDTO> flatten(INodeDTO node, List<INodeDTO> flatList中深度遍历,最后汇总再使用distinct做去重处理得到最终的list结构。

/**
 * Flatten a Tree to a list using recursion(递归实现)
 * @param flatList flatList
 * @return list
 */
 static List<INodeDTO> flatten(List<INodeDTO> flatList){
    return flatList.stream()
        .filter(x -> x.getPid() == null)
        .collect(Collectors.toList())
        .stream()
        .map(x->{return flatten(x,flatList);})
        .flatMap(Collection::stream)
        .distinct()
        .collect(Collectors.toList());
}

/**
 *  recursion
 * @param node  root node
 * @param flatList  flatList
 * @return  list
 */
static List<INodeDTO> flatten(INodeDTO node,  List<INodeDTO> flatList) {
    List<INodeDTO> results = new ArrayList<>();
    if(node != null){
        // get rid of children & parent references
        INodeDTO n = NodeDTO.builder()
            .pid(node.getPid())
            .id(node.getId())
            .build();
        results.add(n);
    }

    List<INodeDTO> children = node.getChildren();
    for (INodeDTO child : children) {
        if(child.getChildren() != null) {
            // Recursive call - Keep flattening until no more children
            List<INodeDTO> flatten = flatten(child, flatList);
            results.addAll(flatten);
        }
    }
    // stop or exit condition
    return results;
}

非递归实现

在非递归,即循环的实现中,我们要用到dequeue数据结构。

deque表示一个双端队列,这意味着可以从队列的两端添加和删除元素。 deque的不同之处在于添加和删除条目的不受限制的特性。

在实现中,ArrayDeque将被用作LIFO(即后进先出)数据结构(即堆栈)。

/**
 * Flatten a Tree to a list using a while Loop instead of recursion
 * @param flatList   flatList
 * @return list
 */
static List<INodeDTO> flatten2(List<INodeDTO> flatList){
    return flatList.stream()
        .filter(x -> x.getPid() == null)
        .collect(Collectors.toList())
        .stream()
        .map(TreeToMapUtils::flatten2)
        .flatMap(Collection::stream)
        .distinct()
        .collect(Collectors.toList());
}

/**
 * . Flatten using a Deque - Double ended Queue
 *
 **/
 static List<INodeDTO> flatten2(INodeDTO node) {

    if (node == null) {
        return null;
    }

    List<INodeDTO> flatList = new ArrayList<>();
    Deque<INodeDTO> q = new ArrayDeque<>();
     //add the root
    q.addLast(node);
    //Keep looping until all nodes are traversed
    while (!q.isEmpty()) {
        INodeDTO n = q.removeLast();
        flatList.add(NodeDTO.builder().id(n.getId()).pid(n.getPid()).build());
        List<INodeDTO> children = n.getChildren();
        if (children != null) {
            for (INodeDTO child : children) {
                q.addLast(child);
            }
        }
    }
    return flatList;
}

实例

在实例中,我们主要用到list to map 中的输出,看是否能用flatten函数还原结构。

public static void main(String[] args) throws JsonProcessingException {
    UseCase useCase = new UseCase();
    List<INodeDTO> results = useCase.listBy("condtion1", "condtion2");
    //convert json with style1 = {NodeDTO@1502} "NodeDTO(id=1, pid=null, children=null)"
    ObjectMapper objectMapper = new ObjectMapper();
    String json = objectMapper.writerWithDefaultPrettyPrinter().writeValueAsString(results);
    System.out.println(json);
    //flatten now
    List<INodeDTO> flatten = TreeToMapUtils.flatten2(results);
    System.out.println(flatten);

}

输出结果不但包含Tree形数据结构,还获取到了list数据,如下图所示,至此,达到效果。

总结

至此,递归和非递归分别实现list to tree tree to list已完成,实现比较仓促,有很多细节处未处理好,希望看到的小伙伴及时指出,不胜感激。

到此这篇关于Java实现平铺列表(List)互转树形(Tree)结构的文章就介绍到这了,更多相关Java List转树形Tree结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JAVA中list,set,数组之间的转换详解

    JAVA的list,set,数组之间的转换,主要是使用Apache Jakarta Commons Collections,具体的方法如下:import org.apache.commons.collections.CollectionUtils; String[] strArray = {"aaa", "bbb", "ccc"};    List strList = new ArrayList();    Set strSet = new Ha

  • java将String字符串转换为List<Long>类型实例方法

    在一些应用场景当中,我们可能会遇到以下的场景,我们要使用的类型是List类型,但是接收到的参数是Stirng类型如1,2,3,4等这样的形式 那么我们可以通过采用以下的代码完成以上需求的转换 private static Log log = LogFactory.getLog(Demo.class); @Test public void test() { String ids = "1, 3, 5, 7, 9"; // 首先去除空格 String idsWithNoBlank = id

  • java 三种将list转换为map的方法详解

    java 三种将list转换为map的方法详解 在本文中,介绍三种将list转换为map的方法: 1) 传统方法 假设有某个类如下 class Movie { private Integer rank; private String description; public Movie(Integer rank, String description) { super(); this.rank = rank; this.description = description; } public Int

  • java8快速实现List转map 、分组、过滤等操作

    利用java8新特性,可以用简洁高效的代码来实现一些数据处理. 定义1个Apple对象: public class Apple { private Integer id; private String name; private BigDecimal money; private Integer num; public Apple(Integer id, String name, BigDecimal money, Integer num) { this.id = id; this.name =

  • java中数组list map三者之间的互转介绍

    三者之间转换关系,一张图清晰呈现.  上代码: 其中的maputils是apache的collection包. 复制代码 代码如下: package util; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import org.apache.commons.collections.MapUtil

  • Java 数组转List的四种方式小结

    目录 第一种方式(未必最佳):使用ArrayList.asList(strArray) 第二种方法(支持增删查改): 第三种方式(通过集合工具类Collections.addAll()方法(最高效)) 第四种方式通过JDK8的Stream流将3总基本类型数组转为List java数组转list误区 一.不能把基本数据类型转化为列表 二.asList方法返回的是数组的一个视图 第一种方式(未必最佳):使用ArrayList.asList(strArray) ​ 使用Arrays工具类Arrays.

  • Java ArrayList 数组之间相互转换

    做研发的朋友都知道,在项目开发中经常会碰到list与数组类型之间的相互转换,本文通过一个简单的例子给大家讲解具有转换过程. Java代码 package test.test1; import java.util.ArrayList; import java.util.List; public class Test { /** * @param args */ public static void main(String[] args) { List list=new ArrayList(); l

  • JSON的String字符串与Java的List列表对象的相互转换

    在前端: 1.如果json是List对象转换的,可以直接遍历json,读取数据. 2.如果是需要把前端的List对象转换为json传到后台,param是ajax的参数,那么转换如下所示: var jsonStr = JSON.stringify(list); var param= {}; param.jsonStr=jsonStr; 在后台: 1.把String转换为List(str转换为list) List<T> list = new ArrayList<T>(); JSONAr

  • Java8 将List转换为用逗号隔开的字符串的多种方法

    1.使用谷歌的Joiner转换 public static <T> String parseListToStr(List<T> list){ String result = Joiner.on(",").join(list); return result; } 2.使用lambda表达式遍历集合 public static <T> String parseListToStr2(List<T> list){ StringBuffer sb

  • Java实现平铺列表(List)互转树形(Tree)结构

    目录 需求 实践List to Tree 递归实现 非递归实现 实例 实践Tree to List 递归实现 非递归实现 实例 总结 很多时候为满足前后端交互的数据结构需求,往往我们需要把平铺的List数据与Tree型层级数据结构进行互转,这篇文章提供详实的递归和非递归的方式去实现数据结构转换,为了使用到lambda的特性,Java version >=8. 需求 我们从基础设施层获取了一个列表数据,列表其中的对象结构如下,注意约束条件如果没有pid,默认为null. @Getter @Sett

  • python实现嵌套列表平铺的两种方法

    方法一:使用列表推导式 >>> vec = [[1,2,3],[4,5,6],[7,8,9]] >>> get = [num for elem in vec for num in elem] >>> get [1, 2, 3, 4, 5, 6, 7, 8, 9] 方法相当于 >>> vec = [[1,2,3],[4,5,6],[7,8,9]] >>> result = [] >>> for ele

  • Java在Excel中添加水印的实现(单一水印、平铺水印)

    在Excel中没有直接添加水印的功能,但依旧可以通过一定方式来实现类似水印效果.本文通过Java程序代码介绍具体实现方法.可添加单一水印效果,即水印是以单个文本字样来呈现:也可添加多个平铺水印效果,即水印是以多个文本字样来页面中平铺.详细内容见下文. 程序环境: 测试文档:Office Excel 2013 编译环境:IntelliJ IDEA 2018 JDK版本:1.8.0 Excel库:Java系列free spire.xls.jar 3.9.1 1.单一水印效果 import com.s

  • Java编程获取文件列表及子文件目录的方法(非递归)

    废话不谈,直接进入正题,理解见代码注释. // 非递归 public List<String> scanFiles(String path) { List<String>filePaths = new ArrayList<String>(); LinkedList<File> list = new LinkedList<File>(); File dir = new File(path); File[] file = dir.listFiles(

  • Java实现拖拽列表项的排序功能

    在一些允许用户自定义栏目顺序的app(如:凤凰新闻.网易云音乐等),我们可以方便地拖拽列表项来完成列表的重新排序,进而完成对栏目顺序的重排.这个功能很人性化,而实现起来其实很简单(甚至都不用写什么后台代码),只有三步. ①把冰箱门打开 首先,我们需要让冰箱的大门敞开,也就是允许我们进行拖拽的相关操作.以ListView为例,注意下面几个属性. <StackPanel> <ListView x:Name="list" AllowDrop="True"

  • Java数据结构之散列表(动力节点Java学院整理)

    基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的

  • Java代码实现Map和Object互转及Map和Json互转

    先给大家介绍下map和object互相转换的代码. 具体代码如所示: /** * 使用org.apache.commons.beanutils进行转换 */ class A { public static Object mapToObject(Map<String, Object> map, Class<?> beanClass) throws Exception { if (map == null) return null; Object obj = beanClass.newI

  • java实现递归文件列表的方法

    本文实例讲述了java实现递归文件列表的方法.分享给大家供大家参考.具体如下: FileListing.java如下: import java.util.*; import java.io.*; /** * Recursive file listing under a specified directory. * * @author javapractices.com * @author Alex Wong * @author anonymous user */ public final cla

  • Android编程实现图片平铺的方法分析

    本文实例讲述了Android编程实现图片平铺的方法.分享给大家供大家参考,具体如下: 1)第一种利用系统提供的api实现 Bitmap bitmap = BitmapFactory.decodeResource(getResources(), R.drawable.pic); //bitmap = Bitmap.createBitmap(100, 20, Config.ARGB_8888); BitmapDrawable drawable = new BitmapDrawable(bitmap)

  • Android实现平铺图片效果

    最近开发App,美工设计了一个有锯齿边沿效果的背景图,只给了我一个锯齿,然后需要平铺展示锯齿效果: android中实现平铺图片有两种方式: (1)在drawable中的drawable文件中定义平铺的Bitmap <?xml version="1.0" encoding="utf-8"?> <bitmap xmlns:android="http://schemas.android.com/apk/res/android" an

随机推荐

其他