本文主要是介绍使用Java实现通用树形结构构建工具类,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...
完整代码
package com.pig4cloud.pigx.common.core.util.tree; import Java.util.*; import java.util.function.Function; import java.util.stream.Collectors; /** * 通用树结构构建工具类 * * <p>重要说明: * <ol> * <li>所有节点必须具有唯一ID</li> * <li>父节点不存在时自动成为根节点</li> * <li>节点排序依赖comparator实现</li> * <li>支持循环依赖检测和错误路径提示</li> * </ol> * * @param <T> 原始数据类型 * @param <K> 节点ID类型(建议使用包装类型) */ public class TreeBuilder<T, K> { private final Function<T, K> idGetter; private final Function<T, K> parentIdGetter; private final ChildSetter<T> childSetter; private final Comparator<T> comparator; /** * 构造方法 */ public TreeBuilder(Function<T, K> idGetter, Function<T, K> parentIdGetter, ChildSetter<T> childSetter, Comparator<T> comparator) { this.idGetter = Objects.requireNonNull(idGetter, "ID获取器不能为null"); this.parentIdGetter = Objects.requireNonNull(parentIdGetter, "父ID获取器不能为null"); this.childSetter = Objects.requireNonNull(childSetter, "子节点设置器不能为null"); this.comparator = Objects.requireNonNull(comparator, "排序比较器不能为null"); } /** * 构建完整树结构 */ public List<T> buildTree(List<T> items) { Objects.requireNonNull(items, "节点列表不能为null"); if (items.isEmpty()) return Collections.emptyList(); // 1. 构建数据索引 Map<K, T> nodeMap = createNodeMap(items); Map<K, List<T>> parentChildrenMap = items.stream() .collect(Collectors.groupingBy( parentIdGetter, LinkedHashMap::new, // 保持插入顺序 Collectors.toList() )); // 2. 循环依赖检测 detectCyclicDependencies(items, nodeMap); // 3. 构建树结构 China编程 nodeMap.forEach((nodeId, node) -> { List<T> children = parentChildrenMap.getOrDefault(nodeId, Collections.emptyList()) .stream() .sorted(comparator) .collect(Collectors.toList()); childSetter.setChildren(node, Collections.unmodifiableList(children)); }); // 4. 获取根节点(parentId为null或不存在于nodeMap) return items.stream() .filter(item -> isRootNode(item, nodeMap)) .sorted(comparator) .collect(Collectors.toList()); } /** * 判断是否为根节点(抽离方法提升可读性) */ private boolean isRootNode(T item, Map<K, T> nodeMap) { K parentId = parentIdGetter.apply(item); return parentId == null || !nodeMap.containsKey(parentId); } /** * 构建搜索结果树 */ public List<T> buildSearchTree(List<T> allItems, Set<K&SxKHNdwgt; matchIds) { Objects.requireNonNull(allItems, "节点列表不能为null"); Objects.requireNonNull(matchIds, "匹配ID集合不能为null"); Set<K> relatedIds = findRelatedIds(allItems, matchIds); List<T> relatedItems = allItems.stream() .filter(item -> relatedIds.contains(idGetter.apply(item))) .collect(Collectors.toList()); return buildTree(relatedItems); } /** * 创建节点ID映射表(含重复检测) */ private Map<K, T> createNodeMap(List<T> items) { Map<K, T> map = new LinkedHashMap<>(items.size()); for (T item : items) { K id = idGetter.apply(item); if (map.containsKey(id)) { throw new IllegalArgumentException(String.format( "发现重复节点ID: %s (冲突对象1: %s, 冲突对象2: %s)", id, map.get(id), item)); } map.put(id, item); } return map; } /** * 循环依赖检测核心逻辑 */ private void detectCyclicDependencies(List<T> items, Map<K, T> nodeMap) { Set<K> verifiedNodes = new HashSet<>(); Map&编程lt;K, K> idToParentMap = items.stream() .collect(Collectors.toMap(idGetter, parentIdGetter)); for (T item : items) { K currentId = idGetter.apply(item); if (verifiedNodes.contains(currentId)) continue; Set<K> path = new LinkedHashSet<>(); K tracingId = currentId; while (tracingId != null) { if (!path.add(tracingId)) { throw new CyclicDependencyException(buildCyclePath(path, tracingId)); } // 短路已验证节点 if (verifiedNodes.contains(tracingId)) break; K parentId = idToParentMap.get(tracingId); if (parentId == null) break; // 直接循环检测 if (parentId.equals(tracingId)) { throw new CyclicDependencyException("直接循环依赖: " + tracingId); } tracingId = parentId; } verifiedNodes.addAll(path); } } /** * 构造循环路径描述 */ private String buildCyclePath(Set<K> path, K duplicateId) { List<K> pathList = new ArrayList<>(path); int index = pathList.indexOf(duplicateId); List<K> cycle = pathList.subList(index, pathList.size()); return "检测到循环依赖链: " + cycle.stream() .map(Object::toString) .collect(Collectors.joining(" → ")); } /** * 查找相关ID集合(匹配节点+路径节点) */ private Set<K> findRelatedIds(List<T> allItems, Set<K> matchIds) { Map<K, K> idToParentMap = allItems.stream() .collect(Collectors.toMap(idGetter, parentIdGetter)); return matchIds.stream() .flatMap(id -> traceAncestors(id, idToParentMap).stream()) .collect(Collectors.toSet()); } /** * 追溯父节点链 */ private Set<K> traceAncestors(K startId, Map<K, K> idToParentMap) { Set<K> ancestors = new LinkedHashSet<>(); K currentId = startId; android while (currentId != null && ancestors.add(currentId)) { currentId = idToParentMap.get(currentId); } return ancestors; } /** * 自定义循环依赖异常 */ public static class CyclicDependencyException extends RuntimeException { public CyclicDependencyException(String message) { super(message); } } /** * 子节点设置接口 */ @FunctionalInterface public interface ChildSetter<T> { void setChildren(T parent, List<T> children); } /* 快捷构造方法 */ public static <T, K> TreeBuilder<T, K> create( Function<T, K> idGetter, Function<T, K> parentIdGetter, ChildSetter<T> childSetter, Comparator<T> comparator) { return new TreeBuilder<>(idGetter, parentIdGetter, childSetter, comparator); } public static <T, K extends Comparable<? super K>> TreeBuilder<T, K> createWithNaturalOrder( Function<T, K> idGetter, Function<T, K> parentIdGetter, ChildSetter<T> childSetter) { return new TreeBuilder<>( idGetter, parentIdGetter, childSetter, Comparator.comparing(idGetter, Comparator.nullsLast(Comparator.naturalOrder())) ); } }
一、设计思想与核心功能
本工具类采用泛型设计,可处理任意类型的节点数据,具备以下核心能力:
- 多类型支持:通过泛型参数T(数据类型)和K(ID类型),支持各种业务场景
- 自动化构建:自动识别根节点、建立父子关系
- 安全防护:内置循环依赖检测、重复ID校验
- 灵活扩展:支持自定义排序规则、子节点设置方式
- 高效查询:提供子树构建功能,适用于搜索场景
二、核心实现原理
1. 数据结构准备阶段
Map<K, T> nodeMap = createNodeMap(items); Map<K, List<T>> parentChildrenMap = items.stream() .collect(Collectors.groupingBy(...));
- 节点映射表:通过ID快速定位节点,验证ID唯一性
- 父子关系映射:预先生成父节点→子节点列表的关系字典
2. 循环依赖检测算法
采用路径追踪法,时间复杂度O(n):
Set<K> path = new LinkedHashSet<>(); while (tracingId != null) { if (!path.add(tracingId)) { throw new CyclicDependencyException(...); } // 追溯父节点链 }
可检测两种异常情况:
- 直接循环:父节点指向自身
- 间接循环:A→B→C→A型循环链
3. 树形结构构建
采用两阶段构建模式:
- 初始化所有节点的子节点列表
- 筛选根节点(父ID不存在或对应节点缺失)
4. 搜索子树生成
通过ID回溯算法构建有效路径:
Set<K> traceAncestors(K startId) { // 向上追溯所有祖先节点 }
确保搜索结果的完整树形结构
三、关键代码详解
1. 节点排序实现
childSetter.setChildren(node, children.stream() .sorted(comparator) .collect(Collectors.toList()) );
支持两种排序方式:
- 自然排序(createWithNaturalOrder)
- 自定义比较器(推荐业务相关排序)
2. 异常处理机制
自定义异常类型增强可读性:
public class CyclicDependencyException extends RuntimeException { // 携带具体循环路径信息 }
提供明确的错误定位信息:
检测到循环依赖链: 1001 → 1002 → 1003 → 1001
3. 函数式接口应用
@FunctionalInterface public interface ChildSetter<T> { void setChildren(T parent, List<T> children); }
使用时可通过Lambda表达式实现:
TreeBuilder<Department, Long> builder = new TreeBuilder<>(..., (parent, children) -> parent.setChildDepts(children));
四、使用示例
基础用法
List<Menu> menus = getFromDB(); TreeBuilder<Menu, Integer> builder = TreeBuilder.create( Menu::getId, Menu::getParentId, (parent, children) -> parent.setChildren(children), Comparator.comparing(Menu::getSortOrder) ); List<Menu> tree = builder.buildTree(menus);
搜索场景应用
Set<Integer> matchIds = searchService.findIds("关键"); List<Menu> resultTree = builder.buildSearchTree(allMenus, matchIds);
五、注意事项
- ID规范:
- 必须实现有效的hashCode()和equals()
- 推荐使用包装类型(避免Long与long的匹配问题)
- 对象状态:
- 原始数据对象应支持子节点集合设置
- 建议China编程使用不可变集合防止意外修改
- 特殊场景:
- 空集合处理返回emptyList()
- 允许游离节点(父节点不存在时成为根节点)
- 性能考量:
- 万级数据量建议分批处理
- 频繁构建时可缓存nodeMap
以上就是使用Java实现通用树形结构构建工具类的详细内容,更多关于Java构建树形结构的资料请关注编程China编程(www.chinasem.cn)其它相关文章!
这篇关于使用Java实现通用树形结构构建工具类的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!