Java树结构

java , , , , 评论

前言

很久不写业务接口, 最近刚好遇到需要实现树结构, 做下简单总结

逻辑实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package com.easyliao.demo;

import com.fasterxml.jackson.databind.ObjectMapper;
import lombok.Data;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author cuishiying
 * @date 2021-06-17
 */
public class TreeTest {

    @Data
    public static class Node {
        private Integer id;
        private String name;
        private Integer pid;
        private List<Node> children;

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

    public static void main(String[] args) throws Exception{
        Node p0 = new Node(1, "p00", 0);
        Node p1 = new Node(2, "p01", 0);
        Node p2 = new Node(3, "p10", 1);
        Node p3 = new Node(4, "p11", 1);
        Node p4 = new Node(5, "p20", 3);
        List<Node> nodes = Arrays.asList(p0, p1, p2, p3, p4);
        List<Node> tree = buildTree(nodes);

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

    }

    /**
     * 单个根节点
     * @param pidList 平铺list
     * @return 树结构
     */
    public Node buildOneNodeTree(List<Node> pidList){
        // pid -> children
        Map<Integer,List<Node>> pidListMap = pidList.stream().collect(Collectors.groupingBy(Node::getPid));
        pidList.forEach(item->item.setChildren(pidListMap.get(item.getId())));
        // 取出顶层节点的对象，本例顶层节点的"PID"为0
        return pidListMap.get(0).get(0);
    }

    /**
     * 多个顶层节点
     * @param pidList 平铺list
     * @return 树结构
     */
    public static List<Node> buildTree(List<Node> pidList){
        // pid -> children
        Map<Integer,List<Node>> pidListMap = pidList.stream().collect(Collectors.groupingBy(Node::getPid));
        // 在内存中为同一对象, 所以set后分组也会生效
        pidList.forEach(item->item.setChildren(pidListMap.get(item.getId())));
        // 返回结果也改为返回顶层节点的list, 顶层节点的pid=0
        return pidListMap.get(0);
    }

}

简单抽象

我们这里做一个简单工具类

  1. 首先我们抽象一个接口, 所有实现Tree结构的对象需要实现该接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @author cuishiying
 * @date 2021-01-22
 */
public interface TreeNode<T> {

    /**
     * 获取节点id
     *
     * @return 树节点id
     */
    T getId();

    /**
     * 获取该节点的父节点id
     *
     * @return 父节点id
     */
    T getPid();

    /**
     * 设置节点的子节点列表
     *
     * @param children 子节点
     */
    void setChildren(List<? extends TreeNode<T>> children);

    /**
     * 获取所有子节点
     *
     * @return 子节点列表
     */
    List<? extends TreeNode<T>> getChildren();
}
  1. 定义基本实现类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @author cuishiying
 * @date 2021-01-22
 */
@Data
public class Node implements TreeNode{

    private Integer id;
    private String name;
    private Integer pid;
    private List<Node> children;

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

    @Override
    public Object getId() {
        return id;
    }

    @Override
    public Object getPid() {
        return pid;
    }

    @Override
    public List<? extends TreeNode> getChildren() {
        return children;
    }

    @Override
    public void setChildren(List children) {
        this.children = children;
    }
}
  1. 工具类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 * @author cuishiying
 * @date 2021-01-22
 */
public class TreeBuilder {

    public static List<? extends TreeNode> build(List<? extends TreeNode> nodes) {
        // pid -> children
        Map<Object, ? extends List<? extends TreeNode>> pidListMap = nodes.stream().collect(Collectors.groupingBy(TreeNode::getPid));
        // 在内存中为同一对象, 所以set后分组也会生效
        nodes.forEach(item->item.setChildren(pidListMap.get(item.getId())));
        // 返回结果也改为返回顶层节点的list, 顶层节点的pid=0
        return pidListMap.get(0);
    }
}
  1. 测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @author cuishiying
 * @date 2021-01-22
 */
public class TreeTest {

    public static void main(String[] args) throws Exception {
        Node p0 = new Node(1, "p00", 0);
        Node p1 = new Node(2, "p01", 0);
        Node p2 = new Node(3, "p10", 1);
        Node p3 = new Node(4, "p11", 1);
        Node p4 = new Node(5, "p20", 3);
        List<Node> nodes = Arrays.asList(p0, p1, p2, p3, p4);
        List<Node> tree = (List<Node>) TreeBuilder.build(nodes);

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

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
[{
    "id": 1,
    "name": "p00",
    "pid": 0,
    "children": [{
        "id": 3,
        "name": "p10",
        "pid": 1,
        "children": [{
            "id": 5,
            "name": "p20",
            "pid": 3,
            "children": null
        }]
    }, {
        "id": 4,
        "name": "p11",
        "pid": 1,
        "children": null
    }]
}, {
    "id": 2,
    "name": "p01",
    "pid": 0,
    "children": null
}]

最后

欢迎大家关注公众号【当我遇上你】支持我。

当我遇上你

勿在浮沙筑高楼