当前位置：首页 > news >正文

java最优建树算法

news 2025/8/8 1:20:45

建树算法

树的数据结构

{"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());}

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

优化后的建树方式

方式一

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

优点：

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

缺点：

只能处理一级父子关系：该算法只能处理一级父子关系，即每个节点只能有一个直接父节点。如果存在多级父子关系，该算法无法处理。
需要额外的存储空间：该算法需要使用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;
}