java最优建树算法

建树算法

树的数据结构

{
    "code": "1111",
    "name": "",
    "parentcode": "0000",
    "children": null
},	
{
    "code": "2222",
    "name": "",
    "parentcode": "0000",
    "children": [
        {
            "code": "1234",
            "name": "",
            "parentcode": "2222",
            "children": null
        },
        {
            "code": "4561",
            "name": "",
            "parentcode": "2222",
            "children": [
                "code": "7894",
           		"name": "",
            	"parentcode": "4561",
            	"children": null
            ]
        }
    ]
}
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

常见建树方式

    public List<TreeNodeInfo> getChildren(List<TreeNodeInfo> infos, String id) {
        return infos.stream()
                .filter(g -> Objects.equals(g.getParentid(), id))
                .map(g -> {
                    List<TreeNodeInfo> children = getChildren(infos, g.getId());
                    g.setChildren(children);
                    return g;
                }).collect(Collectors.toList());
    }
1
2
3
4
5
6
7
8
9

1. 效率问题：在每一层递归中，都需要遍历整个节点列表来查找匹配的子节点。这样的操作可能会导致性能下降，尤其是当节点列表很大时。时间复杂度为O(n^2)
2. 内存消耗：递归算法需要不断地创建新的函数调用栈，每次递归调用都会占用一定的内存空间。对于大型树结构或节点列表，递归调用可能导致栈溢出或占用过多的内存。
3. 重复遍历：在每一层递归中，都需要遍历整个节点列表来查找匹配的子节点。这意味着同一个节点可能会被多次遍历，导致了重复的工作。
4. 综上所述，该建树算法在处理小型、非循环引用的节点列表时可能是有效的，但在处理大型、存在循环引用或需要排序的节点列表时可能存在一些缺点

优化后的建树方式

方式一

    public List<TreeNodePO> getTree1(List<TreeNodePO> nodes) {

        int initialCapacity = (int) (allInfos.size() / 0.75 + 1);
        Map<String, TreeNodePO> map = new HashMap<>(initialCapacity);
        for (TreeNodePO info : nodes) {
            map.put(info.getCode(), info);
        }
        List<TreeNodePO> roots = new ArrayList<TreeNodePO>();
        String pid = null;
        TreeNodePOpNode = null;
        for (TreeNodePO node : nodes) {
            pid = node.getParentcode();
            //根节点标识
            if (Objects.equals(pid, "0000")) {
                roots.add(node);
                continue;
            }
            pNode = map.get(pid);
            if (pNode != null) {
                pNode.addChildren(node);
            }
        }
        return roots;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

优点：

1. 时间效率高：使用了HashMap来存储节点信息，通过节点的code作为key，可以快速查找到对应的节点，因此在构建树的过程中，可以快速地找到父节点并将子节点添加到父节点的children列表中，时间复杂度为O(n)。
2. 空间效率高：使用了HashMap来存储节点信息，通过节点的code作为key，可以避免重复存储相同的节点，节省了存储空间。

缺点：

1. 只能处理一级父子关系：该算法只能处理一级父子关系，即每个节点只能有一个直接父节点。如果存在多级父子关系，该算法无法处理。
2. 需要额外的存储空间：该算法需要使用HashMap来存储节点信息，需要额外的存储空间来存储节点的code和对应的节点对象，可能会占用较多的内存空间

方式二

public List<TreeNodePO> getTree2(List<TreeNodePO> allInfos) {
    // 创建缓存，用于存储已构建的节点
    int initialCapacity = (int) (allInfos.size() / 0.75 + 1);
    Map<String, TreeNodePO> cache = new HashMap<>(initialCapacity);

    //构建树
    List<TreeNodePO> roots = new ArrayList<>();
    for (TreeNodePO info : allInfos) {
        String code = info.getCode();
        String parentcode = info.getParentcode();
        //如果存在则get取出，不存在则put放入
        TreeNodePO node = cache.computeIfAbsent(code, TreeNodePO::new);
        node.setName(info.getName());
        node.setParentcode(info.getParentcode());

		//根节点标识
        if (Objects.equals(parentcode, "0000")) {
            roots.add(node);
        } else {
            TreeNodePO parentNode = cache.computeIfAbsent(parentcode, TreeNodePO::new);
            parentNode.addChildren(info);
        }
    }
    return roots;
}
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

优点：

1. 时间效率高：使用HashMap作为缓存，可以快速查找和存储节点，避免了遍历查找的时间消耗，时间复杂度为O(n)。
2. 空间效率高：使用HashMap作为缓存，可以避免重复构建相同的节点，减少了内存占用。
3. 算法简洁易懂：通过使用HashMap的方式构建树结构，代码逻辑清晰，易于理解和维护。

缺点：

1. 依赖HashMap：该算法依赖于HashMap作为缓存结构，如果数据量很大，可能会导致HashMap的内存占用过高，影响性能。
2. 无法处理循环依赖：如果存在循环依赖的情况，即节点A的父节点是节点B，节点B的子节点是节点A，该算法无法处理，可能会导致死循环或树结构错误。

5w条测试数据算法耗时：

5w条测试数据算法空间占用