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

2025-03-29 02:50

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



http://www.chinasem.cn/article/1153999

相关文章

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR?第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先,会用到 函数式接口 Consumer, 通过这个可以解耦回调方法,下面先写一个

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Qt中QGroupBox控件的实现

《Qt中QGroupBox控件的实现》QGroupBox是Qt框架中一个非常有用的控件,它主要用于组织和管理一组相关的控件,本文主要介绍了Qt中QGroupBox控件的实现,具有一定的参考价值,感兴趣... 目录引言一、基本属性二、常用方法2.1 构造函数 2.2 设置标题2.3 设置复选框模式2.4 是否

Qt中QUndoView控件的具体使用

《Qt中QUndoView控件的具体使用》QUndoView是Qt框架中用于可视化显示QUndoStack内容的控件,本文主要介绍了Qt中QUndoView控件的具体使用,具有一定的参考价值,感兴趣的... 目录引言一、QUndoView 的用途二、工作原理三、 如何与 QUnDOStack 配合使用四、自

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St