1. 理解树形结构与业务场景
在企业组织管理中，部门通常具有层级关系，例如一个公司下设多个部门，而某些部门本身也可能包含子部门，这自然形成了一个树形结构。为了在java中表示这种结构并对其进行操作，我们可以定义如下接口：
import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;
/**
* 部门接口，定义了部门的基本属性和行为。
*/
public interface Department {
String getName(); // 获取部门名称
String getType(); // 获取部门类型
/**
* 默认方法：检查当前部门是否匹配给定谓词。
* 此方法仅检查当前节点，不涉及子部门的遍历。
* @param predicate 用于测试部门的条件
* @return 如果匹配则返回包含当前部门的Optional，否则返回空的Optional
*/
default Optional getMatchingDepartment(Predicate predicate) {
if (predicate.test(this)) {
return Optional.of(this);
}
return Optional.empty();
}
} /**
* 公司接口，继承自Department，并表示一个可以包含子部门的实体。
* 它构成了树形结构中的内部节点。
*/
public interface Company extends Department {
List getDepartments(); // 获取当前公司下的所有子部门
/**
* 默认方法：尝试查找当前公司直接子部门中第一个匹配谓词的部门。
* 注意：此方法仅遍历直接子部门，不进行深度递归。
* @param predicate 用于测试部门的条件
* @return 如果找到匹配的直接子部门则返回包含该部门的Optional，否则返回空的Optional
*/
default Optional getMatchingDepartment(Predicate predicate) {
// 此实现仅遍历直接子部门，不深入到子部门的子部门
return getDepartments().stream()
.map(department -> department.getMatchingDepartment(predicate))
.filter(Optional::isPresent)
.map(Optional::get)
.findFirst();
}
} 我们的目标是实现一个功能，能够根据给定的部门类型，从整个公司层级结构中找出所有匹配的部门。
2. 深度优先搜索（DFS）的挑战与解决方案
在上述接口中，Company接口的getMatchingDepartment默认实现只能遍历其直接子部门，无法深入到子部门的子部门，因此无法实现整个树的深度搜索。要解决这个问题，我们需要采用深度优先搜索（DFS）策略，这通常可以通过递归或迭代两种方式实现。
2.1 递归式深度优先搜索
递归是实现树形结构深度遍历最直观的方式之一。其核心思想是：对于当前节点，首先检查自身是否符合条件；如果当前节点是一个可以包含子节点的类型（例如Company），则对其所有子节点递归调用相同的查找逻辑。
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;
import java.util.stream.Stream;
/**
* Concern 类用于封装部门查找逻辑。
* 假设 Concern 内部持有一个根部门列表，代表整个组织的顶层结构。
*/
public class Concern {
private final List rootDepartments; // 假设这是整个组织的顶层部门列表
public Concern(List rootDepartments) {
this.rootDepartments = rootDepartments;
}
/**
* 根据部门类型查找所有匹配的部门（递归实现）。
*
* @param type 要查找的部门类型
* @return 匹配指定类型的所有部门列表
*/
public List findDepartmentByType(String type) {
ArrayList result = new ArrayList<>();
// 从根部门开始递归查找
findDepartmentByTypeRecursiveImpl(type, rootDepartments, result);
return result;
}
/**
* 递归辅助方法：深度遍历部门树，查找指定类型的部门。
*
* @param type 要查找的部门类型
* @param departments 当前需要遍历的部门列表
* @param result 用于收集匹配部门的列表
*/
private void findDepartmentByTypeRecursiveImpl(String type, List departments, List result) {
if (departments == null || departments.isEmpty()) {
return; // 递归终止条件：当前列表为空
}
for (Department current : departments) {
// 1. 检查当前部门是否匹配类型
if (type.equals(current.getType())) {
result.add(current);
}
// 2. 如果当前部门是公司类型，则递归遍历其子部门
if (current instanceof Company) {
findDepartmentByTypeRecursiveImpl(type, ((Company) current).getDepartments(), result);
}
}
}
// 以下是原始问题中提供的其他查找方法，为保持上下文完整性保留
public Optional findDepartmentByName(String name) {
return findDepartmentByPredicate(department -> department.getName().equals(name)).findFirst();
}
private Stream findDepartmentByPredicate(Predicate predicate) {
// 此处的实现需要改进，它依赖于 Department 和 Company 接口中的 getMatchingDepartment 默认方法，
// 但这些默认方法在原始问题中未能实现深度遍历。
// 一个更完整的 findDepartmentByPredicate 应该也使用递归或迭代来遍历整个树。
// 为了演示，此处假设它能某种方式获取到所有部门并进行过滤，但实际应用中需要重新实现深度遍历逻辑。
return rootDepartments.stream() // 假设这里能获取到所有部门的流
.flatMap(dept -> {
// 这是一个简化的示例，实际需要一个深度遍历并扁平化的方法
// 例如：getAllDepartmentsFlatStream().filter(predicate)
return dept.getMatchingDepartment(predicate).stream();
});
}
} 递归实现解析：
立即学习“Java免费学习笔记（深入）”；
- findDepartmentByType(String type) 是公共入口方法，它初始化一个结果列表并调用私有的辅助方法 findDepartmentByTypeRecursiveImpl。
- findDepartmentByTypeRecursiveImpl 是递归的核心。它遍历当前部门列表：
- 对于每个current部门，首先检查其类型是否与目标type匹配。如果匹配，则将其添加到结果列表中。
- 接着，通过 instanceof Company 判断current是否是一个Company（即一个内部节点，可能包含子部门）。
- 如果current是Company，则递归调用 findDepartmentByTypeRecursiveImpl，传入该Company的子部门列表，继续向下遍历。
- 递归的终止条件是当传入的部门列表为空时，或者当遍历到叶子节点（非Company类型的Department）时，递归路径自然结束。
注意事项：
- 递归深度过大可能导致栈溢出（StackOverflowError），尤其是在处理非常深的树形结构时。
- 需要一个辅助方法来隐藏递归的实现细节，保持公共接口的简洁。
2.2 迭代式深度优先搜索（使用栈）
迭代方式实现深度优先搜索通常使用一个显式的栈（Stack）数据结构来模拟递归调用的过程。这种方法可以避免递归深度过大导致的栈溢出问题。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack; // Java 传统的 Stack 类，也可以使用 ArrayDeque
// ... Concern 类的其他部分保持不变 ...
public class Concern {
private final List rootDepartments;
public Concern(List rootDepartments) {
this.rootDepartments = rootDepartments;
}
/**
* 根据部门类型查找所有匹配的部门（迭代实现）。
*
* @param type 要查找的部门类型
* @return 匹配指定类型的所有部门列表
*/
public List findDepartmentByTypeIterative(String type) {
ArrayList result = new ArrayList<>();
Stack stack = new Stack<>(); // 使用 Stack 模拟递归栈
// 将所有根部门压入栈中，作为遍历的起点
// 注意：这里需要确保按照正确的顺序入栈，以模拟DFS的遍历顺序
// 如果希望从左到右遍历，通常需要反向入栈
for (int i = rootDepartments.size() - 1; i >= 0; i--) {
stack.push(rootDepartments.get(i));
}
// 或者更简单地，直接添加所有，但要注意后续处理顺序
// stack.addAll(rootDepartments); // 如果使用 ArrayList 作为栈，添加到末尾，然后从末尾移除
while (!stack.isEmpty()) {
Department current = stack.pop(); // 弹出栈顶部门进行处理
// 1. 检查当前部门是否匹配类型
if (type.equals(current.getType())) {
result.add(current);
}
// 2. 如果当前部门是公司类型，将其子部门压入栈中
if (current instanceof Company) {
List children = ((Company) current).getDepartments();
// 将子部门反向压入栈中，以确保在下次迭代时，按照从左到右的顺序处理子部门
// 或者说，为了保持DFS的特性，后入栈的先处理，所以需要反向入栈
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}
}
return result;
}
// ... 其他方法 ...
} 迭代实现解析：
- findDepartmentByTypeIterative(String type) 是公共入口方法。
- 它初始化一个ArrayList作为结果列表，并创建一个Stack（或java.util.ArrayDeque作为更推荐的栈实现）来存储待访问的部门。
- 首先，将所有根部门压入栈中。为了模拟DFS的从左到右遍历（如果子节点有顺序），通常需要反向压入子节点。
- 进入while循环，只要栈不为空，就持续执行：
- 从栈顶弹出一个Department作为current部门。
- 检查current部门的类型是否匹配，如果匹配则添加到结果列表。
- 如果current部门是Company类型，则获取其所有子部门。
- 将这些子部门反向压入栈中。这样做的目的是，当下次循环弹出时，会先弹出current的第一个子部门，从而实现深度优先的遍历顺序。
注意事项：
- 迭代方式避免了递归深度限制，但在极端情况下，显式栈可能会占用较多内存。
- 使用java.util.ArrayDeque作为栈通常比java.util.Stack性能更好，因为它基于数组实现，避免了同步开销。
- 入栈和出栈的顺序对于遍历的顺序（前序、中序、后序）至关重要。此处实现的是前序遍历（先处理当前节点，再处理子节点）。
3. 总结
本文详细介绍了在Java中遍历树形结构以查找特定类型部门的两种主要深度优先搜索实现方式：递归和迭代。
- 递归方式简洁直观，易于理解，但可能面临栈溢出的风险。它通过一个辅助方法实现，将遍历逻辑封装起来。
- 迭代方式通过显式使用栈来管理遍历状态，避免了递归深度限制，更适合处理非常深或动态变化的树形结构。它需要更精细地控制元素的入栈和出栈顺序。
在实际开发中，选择哪种方法取决于具体的业务场景和对性能、内存以及代码可读性的权衡。对于大多数中等深度的树，递归通常是更简洁的选择；而对于深度不可预测或需要严格控制内存使用的场景，迭代方式则更为稳健。
