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

本文主要是介绍使用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实现通用树形结构构建工具类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

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

目录

完整代码

一、设计思想与核心功能

二、核心实现原理

1. 数据结构准备阶段

2. 循环依赖检测算法

3. 树形结构构建

4. 搜索子树生成

三、关键代码详解

1. 节点排序实现

2. 异常处理机制

3. 函数式接口应用

四、使用示例

基础用法

搜索场景应用

五、注意事项

相关文章

SpringBoot结合Docker进行容器化处理指南

深入理解Go语言中二维切片的使用

Linux下删除乱码文件和目录的实现方式

Spring Boot spring-boot-maven-plugin 参数配置详解(最新推荐)

prometheus如何使用pushgateway监控网路丢包

SpringBoot+EasyExcel实现自定义复杂样式导入导出

mybatis执行insert返回id实现详解

Spring Boot集成Druid实现数据源管理与监控的详细步骤

Python通用唯一标识符模块uuid使用案例详解

Linux在线解压jar包的实现方式