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]}]
}

常见建树方式

    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. 效率问题：在每一层递归中，都需要遍历整个节点列表来查找匹配的子节点。这样的操作可能会导致性能下降，尤其是当节点列表很大时。时间复杂度为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. 时间效率高：使用了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. 时间效率高：使用HashMap作为缓存，可以快速查找和存储节点，避免了遍历查找的时间消耗，时间复杂度为O(n)。
2. 空间效率高：使用HashMap作为缓存，可以避免重复构建相同的节点，减少了内存占用。
3. 算法简洁易懂：通过使用HashMap的方式构建树结构，代码逻辑清晰，易于理解和维护。

缺点：

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

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

算法\次数	1	2	3	4	5	6	7	8	9	10	平均耗时（ms）
getTree1	18	18	17	17	18	18	18	18	18	19	17.9
getTree2	15	14	15	15	14	15	15	15	14	16	14.8

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

算法\次数	1	2	3	4	5	6	7	8	9	10	平均占用空间（KB）
getTree1	5853	4127	7534	4051	5052	5121	7916	5915	4127	6443	5614
getTree2	9193	7051	8096	12853	8476	8568	10983	11908	8918	10104	9615