我要评论完整代码
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> 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<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;
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构建树形结构的资料请关注代码网其它相关文章！
发表评论