思路:
(1)先获取到所有根节点,把所有除根结点外的节点作为子节点,然后遍历每一个根节点,进行递归构建此根的子节点。
(2)递归时需要确定一个根节点,以及剩余子节点,如果子节点的父id等于根节点的id,那么就将这个节点加到根节点的children列表中,然后以当前节点作为根节点进行递归,检查是否还有子节点。
(3)关键:如何构建节点,这个节点中应该至少包含三个属性 id、parentId、children
1、思路代码实现
【注意】代码中用到了jackson
,你完全可以将其替换为fastjson
或gson
,甚至不用,直接输出。
【注意】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 封装基类实现
通过上面的代码可以发现,要构建树,id、parentId、children这三个属性缺一不可,如果要让工具类通用,需要先封装一个基类,所有需要转换的实体需要继承此类,而工具代码的实现也基于这个类。
【注意】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
包下的这些接口。