理解树状结构与业务接口
在许多企业应用中，组织结构常以树的形式呈现。例如，一个公司可能包含多个部门，而某些部门本身又可能是一个更大型的“公司”概念，旗下包含更多子部门。为了模拟这种层级关系，我们定义了两个核心接口：
import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;
public interface Department {
String getName();
String getType();
// 初始尝试中的默认方法，用于匹配单个部门
default Optional getMatchingDepartment(Predicate predicate) {
if (predicate.test(this)) {
return Optional.of(this);
}
return Optional.empty();
}
} public interface Company extends Department {
List getDepartments();
// 初始尝试中的默认方法，仅遍历直接子部门
default Optional getMatchingDepartment(Predicate predicate) {
// 首先检查当前Company自身是否匹配
if (predicate.test(this)) {
return Optional.of(this);
}
// 然后尝试在其直接子部门中查找第一个匹配项
return getDepartments().stream()
.map(department -> department.getMatchingDepartment(predicate))
.filter(Optional::isPresent)
.map(Optional::get)
.findFirst();
}
} 其中，Company接口继承自Department，并额外提供了getDepartments()方法，返回其包含的子部门列表，这正是构成树状结构的关键。我们的目标是，给定一个部门类型（type），从整个树状结构中找出所有匹配该类型的Department实例。
初始的getMatchingDepartment默认方法虽然能够处理当前部门或其直接子部门，但无法深入遍历整个树状层级，这是我们需要解决的核心问题。
递归实现：深度优先搜索
递归是处理树形结构问题最直观且常用的方法之一。通过定义一个函数，该函数在访问当前节点后，会对其所有子节点进行相同的操作，从而实现深度优先搜索（DFS）遍历。
实现思路
- 定义一个公共入口方法，接收要查找的类型，并初始化一个结果列表。
- 定义一个私有的辅助递归方法，它接收当前要遍历的部门列表、要查找的类型以及用于收集结果的列表。
- 在辅助方法中，遍历当前部门列表中的每个部门：
- 如果当前部门的类型与目标类型匹配，则将其添加到结果列表中。
- 如果当前部门是一个Company实例（即它有子部门），则递归调用辅助方法，传入该Company的子部门列表。
示例代码
import java.util.ArrayList;
import java.util.List;
public class OrganizationSearch {
// 假设 Concern 类中包含一个根部门列表
private List rootDepartments;
public OrganizationSearch(List rootDepartments) {
this.rootDepartments = rootDepartments;
}
/**
* 公共入口方法：通过递归查找所有指定类型的部门。
* @param type 要查找的部门类型。
* @return 匹配指定类型的所有部门列表。
*/
public List findDepartmentByTypeRecursive(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) {
// 检查当前部门是否匹配指定类型
if (type.equals(current.getType())) {
result.add(current);
}
// 如果当前部门是Company，则继续递归遍历其子部门
if (current instanceof Company) {
findDepartmentByTypeRecursiveImpl(type, ((Company) current).getDepartments(), result);
}
}
}
} 注意事项
- 递归深度： 递归方法在处理非常深的树结构时，可能会导致栈溢出（StackOverflowError）。Java虚拟机对栈深度有限制。
- 代码简洁性： 对于树形结构，递归实现通常更符合人类的思维模式，代码逻辑清晰。
- 性能： 在大多数情况下，递归和迭代的性能差异不显著，但递归调用的开销略高于迭代。
迭代实现：使用栈模拟深度优先搜索
为了避免递归可能带来的栈溢出问题，我们可以使用一个显式的数据结构（如栈或队列）来模拟树的遍历过程。对于深度优先搜索，通常使用栈。
立即学习“Java免费学习笔记（深入）”；
实现思路
- 定义一个公共入口方法，接收要查找的类型，并初始化一个结果列表。
- 创建一个ArrayList作为栈，并将根部门列表中的所有部门添加到栈中。
- 进入一个循环，只要栈不为空，就持续执行：
- 从栈中移除一个部门（通常是最后一个元素，模拟栈的LIFO特性）。
- 检查该部门的类型是否与目标类型匹配，如果匹配则添加到结果列表中。
- 如果该部门是一个Company实例，则将其所有子部门添加到栈中，以便后续处理。
示例代码
import java.util.ArrayList;
import java.util.List;
public class OrganizationSearch {
private List rootDepartments;
public OrganizationSearch(List rootDepartments) {
this.rootDepartments = rootDepartments;
}
/**
* 公共入口方法：通过迭代查找所有指定类型的部门。
* @param type 要查找的部门类型。
* @return 匹配指定类型的所有部门列表。
*/
public List findDepartmentByTypeIterative(String type) {
ArrayList result = new ArrayList<>();
// 使用ArrayList模拟栈，存储待处理的部门
ArrayList stack = new ArrayList<>();
stack.addAll(rootDepartments); // 将所有根部门压入栈中
// 当栈不为空时，持续进行遍历
while (!stack.isEmpty()) {
// 弹出栈顶元素（最后一个元素）
Department current = stack.remove(stack.size() - 1);
// 检查当前部门是否匹配指定类型
if (type.equals(current.getType())) {
result.add(current);
}
// 如果当前部门是Company，则将其所有子部门压入栈中
// 注意：为了保持DFS顺序，通常会将子部门逆序压入栈，
// 但在这里，由于我们只是收集所有匹配项，顺序不严格要求，
// 只要最终所有子部门都被访问即可。
if (current instanceof Company) {
// 将子部门添加到栈中，它们将在后续循环中被处理
// 为了保持与递归相似的遍历顺序（左子树优先），可以逆序添加
List subDepartments = ((Company) current).getDepartments();
for (int i = subDepartments.size() - 1; i >= 0; i--) {
stack.add(subDepartments.get(i));
}
// 或者直接 stack.addAll(subDepartments); 如果顺序不重要，但可能会改变DFS的访问顺序
}
}
return result;
}
} 注意事项
- 避免栈溢出： 迭代方法不会受限于调用栈的深度，因此可以处理任意深度的树结构。
- 内存使用： 显式栈可能会占用更多内存，尤其是在处理宽度很大的树时。
- 复杂性： 迭代实现通常比递归实现稍微复杂一些，需要手动管理栈的状态。
- 遍历顺序： 迭代实现可以灵活地调整为深度优先（使用栈）或广度优先（使用队列）搜索。上述示例是深度优先搜索。
总结
在Java中遍历树状结构并查找特定类型的元素，可以采用递归或迭代两种主要方法。递归方法简洁直观，适用于大多数情况，但需注意栈溢出风险。迭代方法通过显式使用栈（或队列）来模拟遍历过程，能够有效避免栈溢出问题，适用于处理深度较大的树结构。选择哪种方法取决于具体的场景需求、树的深度以及对代码可读性和性能的要求。在实际开发中，理解并掌握这两种遍历策略对于处理复杂的层级数据至关重要。
