实现一个通用的树形结构构建工具

---

1. 前言

树结构的生成在项目中应该都比较常见，比如部门结构树的生成，目次结构树的生成，但是各人有没有想过，假如在一个项目中有多个树结构，那么每一个都要定义一个生成方法显然是比较麻烦的，以是我们就想写一个通用的生成树方法，下面就来看下如何来写。

2. 树结构

看上面的图，每一个节点都会有三个属性

• parentId 表示父节点 ID，根节点的父结点 ID = null
  
• id 表示当前节点 ID，这个 ID 用来标识一个节点
  
• children 是当前节点的子节点
  

那么上面来介绍完基本的几个属性，下面就来看下详细的实现了。

3. 详细实现逻辑

3.1 TreeNode

TreeNode 是公共节点，就是顶层父类，内里的属性就是上面图中的三个。

1. @Data
2. @AllArgsConstructor
3. @NoArgsConstructor
4. @Accessors(chain = true)
5. public class TreeNode<T, V> {
7.     private T parentId;
9.     private T id;
11.     private List<TreeNode<T, V>> children;
13.     public TreeNode(T parentId, T id) {
14.         this.parentId = parentId;
15.         this.id = id;
16.     }
18.     public void addChild(TreeNode<T, V> treeNode){
19.         if(children == null){
20.             children = new ArrayList<>();
21.         }
22.         children.add(treeNode);
23.     }
25. }

复制代码

TreeNode 内里的 id 都是用的范型，其中 T 就是 id 的范例，因为这个 id 有可能是 Long、Int、String … 范例，不一定是 Long。另一个 V 就是详细的节点范例。
利用范型的利益就是扩展性高，不需要把属性写死。

3.2 TreeUtils

这个是工具类，专门实现树的构建以及一些其他的方法，下面一个一个来看。首先是创建立的方法：

1. /**
2. * 构建一棵树
3. *
4. * @param flatList
5. * @param <T>
6. * @param <V>
7. * @return
8. */
9. public static <T, V extends TreeNode<T, V>> List<V> buildTree(List<V> flatList) {
10.     if (flatList == null || flatList.isEmpty()) {
11.         return null;
12.     }
14.     Map<T, TreeNode<T, V>> nodeMap = new HashMap<>();
15.     for (TreeNode<T, V> node : flatList) {
16.         nodeMap.put(node.getId(), node);
17.     }
19.     // 查找根节点
20.     List<V> rootList = new ArrayList<>();
21.     for (V node : flatList) {
22.         // 如果父节点为空，就是一个根节点
23.         if (node.getParentId() == null) {
24.             rootList.add(node);
25.         } else {
26.             // 父节点不为空，就是子节点
27.             TreeNode<T, V> parent = nodeMap.get(node.getParentId());
28.             if (parent != null) {
29.                 parent.addChild(node);
30.             } else {
31.                 rootList.add(node);
32.             }
33.         }
34.     }
36.     return rootList;
37. }

复制代码

整体时间复杂度：O(n)，创建的时间传入节点聚集，然后返回根节点聚集。内里的逻辑是首先放到一个 nodeMap 中，然后遍历传入的聚集，根据 parentId 进行不同的处理。逻辑不难，看注释即可。但是创建立的时间，有时间我们渴望根据某个顺序对树进行排序，比犹如一层的我想根据名字大概 id 进行排序，顺序大概倒序都可以，那么就可以利用下面的方法。

1. /**
2. * 构建一棵排序树
3. *
4. * @param flatList
5. * @param comparator
6. * @param <T>
7. * @param <V>
8. * @return
9. */
10. public static <T, V extends TreeNode<T, V>> List<V> buildTreeWithCompare(List<V> flatList, Comparator<V> comparator) {
11.    if (flatList == null || flatList.isEmpty()) {
12.        return Collections.emptyList(); // 返回空列表而不是null，这通常是一个更好的实践
13.    }
15.    // 子节点分组
16.    Map<T, List<V>> childGroup = flatList.stream()
17.            .filter(v -> v.getParentId() != null)
18.            .collect(Collectors.groupingBy(V::getParentId));
20.    // 找出父节点
21.    List<V> roots = flatList.stream()
22.            .filter(v -> v.getParentId() == null)
23.            .sorted(comparator) // 根据提供的比较器对根节点进行排序
24.            .collect(Collectors.toList());
26.    // 构建树
27.    for (V root : roots) {
28.        buildTreeRecursive(root, childGroup, comparator);
29.    }
31.    return roots;
32. }
34. private static <T, V extends TreeNode<T, V>> void buildTreeRecursive(V parent, Map<T, List<V>> childGroup, Comparator<V> comparator) {
35.     List<V> children = childGroup.get(parent.getId());
36.     if (children != null) {
37.         // 对子节点进行排序
38.         children.sort(comparator);
39.         // 将排序后的子节点添加到父节点中
40.         children.forEach(parent::addChild);
41.         // 递归对子节点继续处理
42.         children.forEach(child -> buildTreeRecursive(child, childGroup, comparator));
43.     }
44. }

复制代码

这内里是利用的递归，实在也可以利用层次遍历的方式来写，大概直接用第一个 buildTree 方法来往内里套也行。
上面这两个是关键的方法，那么下面再给出一些其他的非必要方法，比如查询节点数。下面这个方法就是获取以 root 为根的数的节点数。

1. /**
2. * 查询以 root 为根的树的节点数
3. *
4. * @param root
5. * @param <T>
6. * @param <V>
7. * @return
8. */
9. private static <T, V extends TreeNode<T, V>> long findTreeNodeCount(TreeNode<T, V> root) {
10.     if (root == null) {
11.         return 0;
12.     }
13.     long res = 1;
14.     List<TreeNode<T, V>> children = root.getChildren();
15.     if (children == null || children.isEmpty()) {
16.         return res;
17.     }
18.     for (TreeNode<T, V> child : children) {
19.         res += findTreeNodeCount(child);
20.     }
21.     return res;
22. }

复制代码

上面是传入一个根节点，获取这棵树的节点数，而下面的就是传入一个聚集来分别获取节点数，内里也是调用了上面的 findTreeNodeCount 方法去获取。

1. /**
2. * 查询给定集合的节点数
3. *
4. * @param nodes 根节点集合
5. * @param <T>
6. * @param <V>
7. * @return
8. */
9. public static <T, V extends TreeNode<T, V>> HashMap<V, Long> findTreeNodeCount(List<V> nodes) {
10.     if (nodes == null || nodes.isEmpty()) {
11.         return new HashMap<>(); // 返回空列表而不是null，这通常是一个更好的实践
12.     }
14.     HashMap<V, Long> map = new HashMap<>();
16.     for (V root : nodes) {
17.         map.put(root,  findTreeNodeCount(root));
18.     }
19.     return map;
20. }

复制代码

下面再给一下获取数的深度的方法。

1. // 查找树的最大深度
2. private static <T, V extends TreeNode<T, V>> int getMaxDepthV(TreeNode<T, V> root) {
3.     if (root == null || root.getChildren() == null || root.getChildren().isEmpty()) {
4.         return 1;
5.     }
6.     return 1 + root.getChildren().stream()
7.             .mapToInt(TreeUtils::getMaxDepthV)
8.             .max()
9.             .getAsInt();
10. }
12. public static <T, V extends TreeNode<T, V>> int getMaxDepth(V root) {
13.     return getMaxDepthV(root);
14. }

复制代码

末了，我们拿到一棵树之后，肯定有时间会渴望在内里查找一些具有特定属性的节点，比如某个节点名字是不是以 xx 开头 … ，这时间就可以用下面的方法。

1. // 查找所有具有特定属性的节点
2. public static <T, V extends TreeNode<T, V>> List<V> findAllNodesByProperty(TreeNode<T, V> root, Function<V, Boolean> predicate) {
3.     if (root == null) {
4.         return Collections.emptyList();
5.     }
6.     List<V> result = new ArrayList<>();
7.     // 符合属性值
8.     if (predicate.apply((V) root)) {
9.         result.add((V) root);
10.     }
11.     if (root.getChildren() == null || root.getChildren().isEmpty()) {
12.         return result;
13.     }
14.     for (TreeNode<T, V> child : root.getChildren()) {
15.         result.addAll(findAllNodesByProperty(child, predicate));
16.     }
17.     return result;
18. }

复制代码

好了，方法就这么多了，其他方法假如你感兴趣也可以继续增补下去，那么这些方法是怎么用的呢？范型的利益要怎么体现呢？下面就来看个例子。

3.3 例子

首先我们有一个部门类，内里包罗部门的名字，然后我需要对这个部门聚集来构建一棵部门树。

1. @Data
2. @ToString
3. @NoArgsConstructor
4. public class Department extends TreeNode<String, Department> {
5.     private String name;
7.     public Department(String id, String parentId, String name){
8.         super(parentId, id);
9.         this.name = name;
10.     }
12. }

复制代码

构建的方法如下：

1. public class Main {
2.     public static void main(String[] args) {
3.         List<Department> flatList = new ArrayList<>();
5.         flatList.add(new Department("1", null, "Sales"));
6.         flatList.add( new Department("2", "1", "East Sales"));
7.         flatList.add( new Department("3", "1","West Sales"));
8.         flatList.add( new Department("4", "2","East Sales Team 1"));
9.         flatList.add( new Department("5", "2","East Sales Team 2"));
10.         flatList.add( new Department("6", "3","West Sales Team 1"));
12.         List<Department> departments = TreeUtils.buildTreeWithCompare(flatList, (o1, o2) -> {
13.             return o2.getName().compareTo(o1.getName());
14.         });
15.         Department root = departments.get(0);
16.         List<Department> nodes = TreeUtils.findAllNodesByProperty(root, department -> department.getName().startsWith("East"));
17.         System.out.println(nodes);
19.         System.out.println(TreeUtils.getMaxDepth(root));
21.         System.out.println(TreeUtils.findTreeNodeCount(nodes));
23.     }
25. }

复制代码

可以看下 buildTreeWithCompare 的输出：

其他的输出如下：

1. [Department(name=East Sales), Department(name=East Sales Team 2), Department(name=East Sales Team 1)]
2. 3
3. {Department(name=East Sales)=3, Department(name=East Sales Team 2)=1, Department(name=East Sales Team 1)=1}

复制代码

4. 小结

工具类就写好了，从例子就可以看出范型的利益了，用了范型之后只要实现类继续了 TreeNode，就可以直接用 TreeUtils 内里的方法，而且返回的还是详细的实现类，而不是 TreeNode。





如有错误，欢迎指出！！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。