Java List转树形Tree结构

时间:2022-09-28 青Cheng序员石头的个人资料头像青Cheng序人气:0

很多时候为满足前后端交互的数据结构需求，往往我们需要把平铺的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已完成，实现比较仓促，有很多细节处未处理好，希望看到的小伙伴及时指出，不胜感激。

加载全部内容