树形结构转换工具

通过将带有上下层级的对象的List集合转换成具有上下级层级的树形结构
思想是根据Java地址引用的原理，映射对应的子节点
此方式实现只需要遍历原集合2次，时间复杂度O(1)，相对于递归的方式（时间复杂度O(n^2)）来说，大大减小了开销；

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

public class TreeUtil {
    private TreeUtil() {
    }

    /**
     * 转换树形结构
     * @param source 需要组装的数据
     * @param <P> 第一层数据的parentId，
     *           eg1 id="1" parentId=null ,topParentId=null 则 此数据为第一层数据
     *           eg2 id="1" parentId="i1" ,topParentId=i1 则 此数据为第一层数据
     *           eg3 id="1" parentId="i1" ,topParentId=null 则 此数据不为第一层数据
     * @param <T> 泛型
     * @return 分层之后的列表
     */
    public static <P,T extends Node<T,P>> List<T> transfer(List<T> source, P topParentId){
        List<T> ts = new ArrayList<>(source);
        Iterator<T> iterator = ts.iterator();

        List<T> root = new ArrayList<>();
        //移除根数据,添加至root集合中
        while (iterator.hasNext()){
            T next = iterator.next();
            if (next.isTop(topParentId)){
                root.add(next);
                iterator.remove();
            }
        }

        // 根据每个对象的parentId进行分组，得到 parent -> List<T> 的映射关系
        Map<P, List<T>> parentMap = ts.stream()
                .filter(m->m.getParentId()!=null)
                .collect(Collectors.groupingBy(T::getParentId));
        for (T t : ts) {
            //设置子菜单引用，因此会将相关数据加入其中
            //同时，由于是引用，子菜单也能通过此处正确加入其自身子菜单
            t.setChildren(parentMap.get(t.getId()));
        }
        // 设置根节点的子节点，也是从 parent -> List<T> 关系中获取，
        // List<T>中已经实现了对应子节点的添加，对于每一个节点已经是树形结构了，添加到根中就完成了
        return root.stream().peek(r -> r.setChildren(parentMap.get(r.getId()))).collect(Collectors.toList());
    }
    /**
     * 将树反向变成列表
     * @param tree 树
     * @param <P> id泛型
     * @param <T> 节点泛型
     * @return
     */
    public static  <P,T extends Node<T,P>> List<T> unTransfer(T tree){
        List<T> list = new ArrayList<>();
        list.add(tree);
        if (!CollectionUtils.isEmpty(tree.getChildren())){
            for (T child : tree.getChildren()) {
                list.addAll(unTransfer(child));
            }
        }
        return list;
    }
    /**
     * 从众多树中取回自己的子树
     * @param trees 树集合
     * @param id id
     * @param <P>
     * @param <T>
     * @return
     */
    public static  <P,T extends Node<T,P>> T fetchSubTree(List<T> trees, P id){
        //循环每一节点
        for (T node : trees) {
            //匹配到了则返回
            if (node.getId().equals(id)){
                return node;
            }
            //没有孩子了则此节点中结束查找，返回上一级查找
            if (CollectionUtils.isEmpty(node.getChildren())){
                continue;
            }
            //遍历子节点，递归查找，查找到了则一直往上返回
            T nodeResp = fetchSubTree(node.getChildren(), id);
            if (nodeResp !=null){
                return nodeResp;
            }
        }
        //一直未找到则此列表树中无
        return null;
    }

    /**
     * 获取子树的ID列表集合
     * @param tree 树
     * @param <ID>
     * @param <T>
     * @return
     */
    public static  <ID,T extends Node<T, ID>> List<ID> fetchSubIds(T tree){
        List<ID> ids = new ArrayList<>();
        ids.add(tree.getId());
        List<T> children = tree.getChildren();
        if (CollectionUtils.isNotEmpty(children)){
            for (T child : children) {
                List<ID> subIds = fetchSubIds(child);
                ids.addAll(subIds);
            }
        }
        return ids;
    }




    /**
     * @description 树形对象
     * @author LiuKewen
     * @date 2022/1/6 12:52
     */
    public interface Node<T, ID> {

        /**
         * 当前id
         * @return
         */
        ID getId();

        /**
         * 父id
         * @return
         */
        ID getParentId();

        /**
         * 是否是顶级菜单 一般顶级菜单的父菜单为null或者 0 
         * 此处可以自己实现，主要找到根节点的ID，才能拿到root集合
         * @param p
         * @return
         */
        default boolean isTop(ID p) {
            ID parentId = this.getParentId();
            //默认父菜单id为空则此菜单id为顶层菜单
            if (parentId == null){
                return true;
            }
            //如果id属于int类型，父菜单为0则为顶层菜单
            if (parentId instanceof Integer && (Integer) parentId ==0){
                return true;
            }
            //如果id属于Long类型，父菜单为0L则为顶层菜单
            if (parentId instanceof Long && (Long) parentId == 0L ){
                return true;
            }
            //否则父菜单等于本id，则为顶层菜单
            return p == parentId;
        }

        void setChildren(List<T> children);

        List<T> getChildren();
    }
}