开发者

使用Java实现通用树形结构构建工具类

目录
  • 完整代码
  • 一、设计思想与核心功能
  • 二、核心实现原理
    • 1. 数据结构准备阶段
    • 2. 循环依赖检测算法
    • 3. 树形结构构建
    • 4. 搜索子树生成
  • 三、关键代码详解
    • 1. 节点排序实现
    • 2. 异常处理机制
    • 3. 函数式接口应用
  • 四、使用示例
    • 基础用法
    • 搜索场景应用
  • 五、注意事项

    完整代码

    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. 构建树结构
          编程客栈  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的匹配问题)
    • 对象状态
      • 原始数据对象应支持子节点集合设置
      • 建议编程客栈使用不可变集合防止意外修改
    • 特殊场景
      • 空集合处理返回emptyList()
      • 允许游离节点(父节点不存在时成为根节点)
    • 性能考量
      • 万级数据量建议分批处理
      • 频繁构建时可缓存nodeMap

    以上就是使用Java实现通用树形结构构建工具类的详细内容,更多关于Java构建树形结构的资料请关注编程客栈(www.devze.com)其它相关文章!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜