指南
核心(hutool-core)
树结构(tree)

层级迭代器-HierarchyIterator

# 🎯 简介

HierarchyIterator 是 Hutool 树结构模块中的一个抽象迭代器类，用于遍历层级结构（如树或图）。它实现了 Iterator 接口，支持深度优先和广度优先两种遍历模式，能够将层级结构转换为可迭代的集合，方便使用传统集合操作或 Stream API 进行处理。

# 📋 核心特性

✅ 支持深度优先遍历
✅ 支持广度优先遍历
✅ 支持节点过滤
✅ 支持自定义下一层级节点发现
✅ 实现了 Iterator 接口，可直接用于增强 for 循环
✅ 支持 Stream API 操作
✅ 避免循环引用问题
✅ 根节点不可被过滤
✅ 非侵入式设计，无需修改原有数据结构

# 🛠️ 类结构

typedef HierarchyIterator<T>
  ├── 实现自 Iterator<T>
  ├── 静态内部类
  │   ├── DepthFirst<T>     // 深度优先迭代器
  │   └── BreadthFirst<T>   // 广度优先迭代器
  ├── 属性
  │   ├── elementDiscoverer: Function<T, Collection<T>> // 下一层级节点获取方法
  │   ├── filter: Predicate<T>         // 节点过滤器
  │   ├── accessed: Set<T>             // 已访问节点集合
  │   └── queue: LinkedList<T>         // 待遍历节点队列
  └── 方法
      ├── 静态工厂方法
      │   ├── breadthFirst(root, discoverer, filter): HierarchyIterator<T> // 创建广度优先迭代器
      │   ├── breadthFirst(root, discoverer): HierarchyIterator<T> // 创建不带过滤器的广度优先迭代器
      │   ├── depthFirst(root, discoverer, filter): HierarchyIterator<T> // 创建深度优先迭代器
      │   └── depthFirst(root, discoverer): HierarchyIterator<T> // 创建不带过滤器的深度优先迭代器
      ├── 构造方法
      │   └── HierarchyIterator(root, discoverer, filter) // 抽象构造，初始化迭代器
      ├── 迭代方法
      │   ├── hasNext(): boolean // 是否还有下一个节点
      │   └── next(): T // 获取下一个节点
      └── 抽象方法
          └── collectNextElementsToQueue(nextElements) // 将下一层级节点添加到队列

# 🚀 快速开始

# 基本使用

// 定义节点类
class Node {
    private String id;
    private String name;
    private List<Node> children;

    // 构造方法、getter和setter省略
}

// 创建树结构
Node root = new Node("1", "根节点", new ArrayList<>());
Node node2 = new Node("2", "节点2", new ArrayList<>());
Node node3 = new Node("3", "节点3", new ArrayList<>());
Node node4 = new Node("4", "节点4", new ArrayList<>());
Node node5 = new Node("5", "节点5", new ArrayList<>());

root.getChildren().add(node2);
root.getChildren().add(node3);
node2.getChildren().add(node4);
node2.getChildren().add(node5);

// 深度优先遍历
Console.log("深度优先遍历:");
HierarchyIterator<Node> depthIterator = HierarchyIterator.depthFirst(root, Node::getChildren);
depthIterator.forEachRemaining(node -> Console.log(node.getName()));

// 广度优先遍历
Console.log("\n广度优先遍历:");
HierarchyIterator<Node> breadthIterator = HierarchyIterator.breadthFirst(root, Node::getChildren);
breadthIterator.forEachRemaining(node -> Console.log(node.getName()));

# 使用Stream API

// 创建树结构
Node root = createTree();

// 使用Stream API过滤和排序节点
List<Node> filteredNodes = StreamUtil.iterateHierarchies(root, Node::getChildren)
    .filter(node -> node.getName().contains("关键")) // 过滤包含"关键"的节点
    .sorted(Comparator.comparing(Node::getId)) // 按ID排序
    .collect(Collectors.toList());

// 输出结果
Console.log("过滤后的节点: {}", filteredNodes);

# 📖 详细方法

# 静态工厂方法

# breadthFirst(root, nextDiscoverer, filter)

功能：创建广度优先迭代器
参数：
- root - 根节点，根节点不允许被过滤
- nextDiscoverer - 下一层级节点的获取方法
- filter - 节点过滤器，不匹配的节点及其子树将被忽略
返回值：广度优先迭代器实例
使用场景：需要按层级顺序遍历树结构时使用

示例：

HierarchyIterator<Node> iterator = HierarchyIterator.breadthFirst(root, Node::getChildren, node -> node.isEnabled());

# breadthFirst(root, nextDiscoverer)

功能：创建不带过滤器的广度优先迭代器
参数：
- root - 根节点
- nextDiscoverer - 下一层级节点的获取方法
返回值：广度优先迭代器实例
使用场景：需要遍历所有节点时使用

示例：

HierarchyIterator<Node> iterator = HierarchyIterator.breadthFirst(root, Node::getChildren);

# depthFirst(root, nextDiscoverer, filter)

功能：创建深度优先迭代器
参数：
- root - 根节点，根节点不允许被过滤
- nextDiscoverer - 下一层级节点的获取方法
- filter - 节点过滤器，不匹配的节点及其子树将被忽略
返回值：深度优先迭代器实例
使用场景：需要深入遍历树结构时使用

示例：

HierarchyIterator<Node> iterator = HierarchyIterator.depthFirst(root, Node::getChildren, node -> node.getLevel() <= 3);

# depthFirst(root, nextDiscoverer)

功能：创建不带过滤器的深度优先迭代器
参数：
- root - 根节点
- nextDiscoverer - 下一层级节点的获取方法
返回值：深度优先迭代器实例
使用场景：需要遍历所有节点时使用

示例：

HierarchyIterator<Node> iterator = HierarchyIterator.depthFirst(root, Node::getChildren);

# 迭代方法

# hasNext()

功能：判断是否还有下一个节点
返回值：如果队列不为空则返回true，否则返回false

示例：

while (iterator.hasNext()) {
    Node node = iterator.next();
    // 处理节点
}

# next()

功能：获取下一个节点
返回值：下一个节点
异常：如果没有下一个节点，抛出NoSuchElementException
示例：
```
Node node = iterator.next();
```

# 内部类

# DepthFirst

功能：深度优先迭代器实现
特点：先遍历子节点，再遍历兄弟节点
使用场景：需要深入遍历树结构时使用

# BreadthFirst

功能：广度优先迭代器实现
特点：先遍历同一层级的所有节点，再遍历下一层级
使用场景：需要按层级顺序遍历树结构时使用

# 🎨 使用场景

# 1. 树结构搜索

// 创建部门树
Department rootDept = departmentService.getRootDepartment();

// 搜索所有名称包含"技术"的部门
List<Department> techDepts = StreamUtil.iterateHierarchies(rootDept, Department::getChildren)
    .filter(dept -> dept.getName().contains("技术"))
    .collect(Collectors.toList());

// 输出结果
Console.log("技术部门列表: {}", techDepts);

# 2. 节点统计

// 创建菜单树
Menu rootMenu = menuService.getRootMenu();

// 统计所有启用的菜单数量
long enabledMenuCount = StreamUtil.iterateHierarchies(rootMenu, Menu::getChildren)
    .filter(menu -> menu.isEnabled())
    .count();

// 统计不同类型的菜单数量
Map<String, Long> menuTypeCount = StreamUtil.iterateHierarchies(rootMenu, Menu::getChildren)
    .collect(Collectors.groupingBy(Menu::getType, Collectors.counting()));

Console.log("启用的菜单数量: {}", enabledMenuCount);
Console.log("菜单类型统计: {}", menuTypeCount);

# 3. 树结构转换

// 创建原始树结构
OldTreeNode rootOld = oldTreeService.getRoot();

// 转换为新的树结构
List<NewTreeNode> newTreeNodes = StreamUtil.iterateHierarchies(rootOld, OldTreeNode::getSubNodes)
    .map(oldNode -> {
        NewTreeNode newNode = new NewTreeNode();
        newNode.setId(oldNode.getOldId());
        newNode.setName(oldNode.getTitle());
        newNode.setLevel(oldNode.getDepth());
        return newNode;
    })
    .collect(Collectors.toList());

// 构建新的树结构
List<NewTreeNode> newTree = TreeUtil.build(newTreeNodes, "0", (old, node) -> {
    node.setId(old.getId());
    node.setParentId(old.getParentId());
    node.setName(old.getName());
    node.setWeight(old.getSort());
});

Console.log("转换后的树: {}", newTree);

# 4. 复杂过滤条件

// 创建产品分类树
Category rootCategory = categoryService.getRootCategory();

// 复杂过滤：启用状态，级别小于等于3，包含"热门"标签
List<Category> filteredCategories = StreamUtil.iterateHierarchies(rootCategory, Category::getSubCategories)
    .filter(category -> {
        boolean enabled = category.isEnabled();
        boolean levelOk = category.getLevel() <= 3;
        boolean hasHotTag = category.getTags().contains("热门");
        return enabled && levelOk && hasHotTag;
    })
    .collect(Collectors.toList());

Console.log("过滤后的分类: {}", filteredCategories);

# 💡 注意事项

根节点不可过滤：
- 构造迭代器时，根节点必须通过过滤器，否则会抛出异常
- 根节点是遍历的起点，必须存在
避免循环引用：
- 迭代器使用accessed集合记录已访问的节点，避免循环引用导致的无限循环
- 对于有环图结构，能够正确处理
不支持remove()方法：
- 该迭代器仅用于访问层级结构，不支持修改操作
- 调用remove()方法会抛出UnsupportedOperationException
节点发现函数：
- 节点发现函数用于获取下一层级的节点集合
- 如果返回null，迭代器会视为该节点没有子节点
- 函数返回的集合可以是空集合
过滤器影响：
- 不匹配过滤器的节点及其子树将被忽略
- 过滤器仅影响遍历，不会修改原始树结构
性能考虑：
- 对于大型树结构，建议使用合适的过滤器减少遍历节点数量
- 节点发现函数应高效实现，避免复杂计算

# 🚀 性能优化

对于大型树结构，使用过滤器减少遍历的节点数量
节点发现函数应直接返回子节点集合，避免复杂计算
对于频繁使用的遍历模式，考虑缓存结果
优先使用Stream API的短路操作（如findFirst、anyMatch）

# 🔍 最佳实践

选择合适的遍历模式：
- 广度优先：适合按层级处理，如菜单导航、部门层级展示
- 深度优先：适合深入搜索，如文件系统遍历、递归数据处理
结合Stream API使用：
- 利用Stream API的强大功能进行过滤、映射、排序和收集
- 推荐使用StreamUtil.iterateHierarchies方法直接创建Stream
合理设计过滤器：
- 过滤器应简单高效，避免复杂逻辑
- 对于复杂过滤条件，考虑先遍历再过滤，或使用复合Predicate
避免修改原始数据：
- 迭代器仅用于访问数据，不应在遍历过程中修改原始树结构
- 如果需要修改，建议先收集到列表再处理
使用类型安全的lambda：
- 节点发现函数使用方法引用，提高代码可读性和性能
- 避免使用复杂的匿名lambda表达式

# 📝 总结

HierarchyIterator 是 Hutool 树结构模块中的一个强大工具，它为层级结构（树或图）提供了灵活的迭代能力。通过支持深度优先和广度优先两种遍历模式，以及与 Stream API 的无缝集成，使得开发者可以方便地使用传统集合操作或函数式编程方式处理树结构数据。

无论是树结构搜索、节点统计还是复杂的树结构转换，HierarchyIterator 都能提供高效、简洁的解决方案。它的设计理念是打通图/树结构与传统集合的隔阂，让开发者能够使用熟悉的 API 处理复杂的层级数据。

在实际开发中，建议根据具体需求选择合适的遍历模式，并结合 Stream API 的强大功能，充分发挥 HierarchyIterator 的优势，提高代码的可读性和开发效率。

← 树构建器-TreeBuilder 简介→