如何高效的将结果集组装成树状结构

最近遇到了查询出树状结构返回给前端的场景，最常见的思路就是在数据库中将数据全部查询出来，然后在内存中组装，因此记录下三种组装树状结构的方法并对比下执行效率。

首先先来看下VO的结构（以区划作为例子）：

注意：想要组装一棵树结构，不可或缺的三要素：自身id、父节点id、子节点的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@Data
public class AreaVO implements Serializable {
    private static final long serialVersionUID = 1L;
    /**
     * id
     */
    private Long id;
    /**
     * 区划名称
     */
    private String areaName;
    /**
     * 区划编码
     */
    private String areaCode;
    /**
     * 上一级id
     */
    private Long fatherId;
    /**
     * 子节点
     */
    private List<AreaVO> children;
}

1、双重for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private List<AreaVO> buildTree1(List<AreaVO> list) {
    List<AreaVO> roots = new ArrayList<>();
    for (AreaVO areaVO : list) {
        // 根节点的父Id一般为某个特殊的值
        if (ObjectUtil.equals(0L, areaVO.getFatherId())) {
            roots.add(areaVO);
        }
        // 不断地循环，寻找所有的子节点
        for (AreaVO area : list) {
            if (ObjectUtil.notEqual(0L, area.getFatherId()) &&
                    ObjectUtil.equals(area.getFatherId(), areaVO.getId())) {
                if (ObjectUtil.isNull(areaVO.getChildren())) {
                    areaVO.setChildren(new ArrayList<>());
                }
                areaVO.getChildren().add(area);
            }
        }
    }
    return roots;
}

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
private List<AreaVO> buildTree2(List<AreaVO> list) {
    List<AreaVO> root = new ArrayList<>();
    for (AreaVO area : list) {
        //找到根节点进行处理，找下一级节点
        if (ObjectUtil.equals(area.getFatherId(), 0L)) {
            //把所有的根节点放到一个list
            root.add(this.findChildren(area, list));
        }
    }
    return root;
}

private AreaVO findChildren(AreaVO rootNode, List<AreaVO> list) {
    //这个方法是在找rootNode的所有子节点,然后返回rootNode
    for (AreaVO area : list) {
        if (ObjectUtil.equals(rootNode.getId(), area.getFatherId())) {
            if (ObjectUtil.isNull(rootNode.getChildren())) {
                rootNode.setChildren(new ArrayList<>());
            }
            // 把这个节点作为新的根节点继续向下构造树,再把构造的结果作为rootNode的子节点
            rootNode.getChildren().add(this.findChildren(area, list));
        }
    }
    return rootNode;
}

3、使用Map结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private List<AreaVO> buildTree(List<AreaVO> list) {
    // 最终结果
    List<AreaVO> roots = new ArrayList<>();
    // 将所有元素转换成Map
    Map<Long, AreaVO> map = list.stream().collect(Collectors.toMap(AreaVO::getId, Function.identity()));
    list.forEach(item -> {
        Long parentId = item.getFatherId();
        // 如果找不到上一层级，说明是树的根节点，添加至结果集
       	// 此处也可以看到一个好处，根节点的parentId可以为任意值，不再局限于0等特殊的值
        if (!map.containsKey(parentId)) {
            roots.add(item);
        } else {
            // 有父节点，拿到父节点，将自己添加至父节点下
            AreaVO parentMenuVO = map.get(parentId);
            if (ObjectUtil.isNull(parentMenuVO.getChildren())) {
                parentMenuVO.setChildren(new ArrayList<>());
            }
            // 将自己赋值给父节点的List<children>属性
            parentMenuVO.getChildren().add(item);
        }
    });
    return roots;
}

三种方法的下执行效率对比

数据库大约三万条数据，可以看到三种方法的执行效率根本不在一个数量级，尤其是第三种使用Map方法，效率非常之高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@GetMapping("tree")
public Result getTree() {
    List<Area> list = areaService.list();
    List<AreaVO> areaVo = areaConvert.voListConvertEntityList(list);
    DateTime start2 = DateUtil.date();
    List<AreaVO> root1 = this.buildTree1(areaVo);
    DateTime end2 = DateUtil.date();
    System.out.println("双重for循环方法耗时" + DateUtil.between(start2, end2, DateUnit.MS) + "毫秒");
    DateTime start3 = DateUtil.date();
    List<AreaVO> root2 = this.buildTree2(areaVo);
    DateTime end3 = DateUtil.date();
    System.out.println("递归构建方法耗时" + DateUtil.between(start3, end3, DateUnit.MS) + "毫秒");
    DateTime start1 = DateUtil.date();
    List<AreaVO> root3 = this.buildTree3(areaVo);
    DateTime end1 = DateUtil.date();
    System.out.println("使用Map结构方法耗时" + DateUtil.between(start1, end1, DateUnit.MS) + "毫秒");
    return Result.success();
}

最终结果，四次调用所消耗的时间如下：

双重for循环方法耗时16126毫秒
递归构建方法耗时5767毫秒
使用Map结构方法耗时7毫秒

双重for循环方法耗时13381毫秒
递归构建方法耗时6708毫秒
使用Map结构方法耗时3毫秒

双重for循环方法耗时16368毫秒
递归构建方法耗时6765毫秒
使用Map结构方法耗时3毫秒

双重for循环方法耗时15838毫秒
递归构建方法耗时6855毫秒
使用Map结构方法耗时3毫秒