1. 理解树形结构与搜索目标
在企业组织架构中，部门之间常常存在层级关系，形成一个树形结构。在java中，我们可以通过接口来抽象这种关系：
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) {
return getDepartments().stream()
.map(department -> department.getMatchingDepartment(predicate))
.filter(Optional::isPresent)
.map(Optional::get)
.findFirst();
}
} 在这个结构中，Company可以包含多个Department，而这些Department又可能是Company（即子公司的概念），从而形成一个多层级的树状结构。我们的目标是，给定一个部门类型（type），在整个组织树中找出所有匹配该类型的所有部门。
2. 分析初始尝试及其局限性
在上述Company接口的getMatchingDepartment默认方法中，我们尝试通过流式操作来查找匹配的部门。
public interface Company extends Department {
// ...
default Optional getMatchingDepartment(Predicate predicate) {
return getDepartments().stream()
.map(department -> department.getMatchingDepartment(predicate)) // 对每个子部门调用其自身的getMatchingDepartment
.filter(Optional::isPresent)
.map(Optional::get)
.findFirst(); // 找到第一个匹配项就停止
}
} 这个实现存在两个主要局限性：
- 非深度遍历： getMatchingDepartment方法仅对其直接子部门调用getMatchingDepartment，并不会递归地深入到子部门的子部门中去。这意味着它只能在当前层级进行有限的查找。
- 只返回第一个匹配项： findFirst()操作使得方法在找到第一个符合条件的部门后立即终止，无法收集所有匹配的部门。
为了实现全树的深度遍历并收集所有匹配的部门，我们需要更强大的遍历机制，即递归或迭代方法。
立即学习“Java免费学习笔记（深入）”；
3. 解决方案一：递归深度优先搜索 (DFS)
递归是处理树形结构最直观且优雅的方法之一。深度优先搜索（DFS）通过不断深入子节点，直到达到叶子节点，然后回溯，直到所有节点都被访问。
import java.util.ArrayList;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;
public class OrganizationSearcher {
private List rootDepartments; // 假设这是整个组织结构的根部门列表
public OrganizationSearcher(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) {
// 1. 检查当前部门是否匹配
if (type.equals(current.getType())) {
result.add(current);
}
// 2. 如果当前部门是公司（即有子部门），则递归遍历其子部门
if (current instanceof Company) {
// 向下转型为Company，获取其子部门列表
findDepartmentByTypeRecursiveImpl(type, ((Company) current).getDepartments(), result);
}
}
}
} 实现原理：
- 入口方法 (findDepartmentByTypeRecursive)：初始化一个空的ArrayList来存储结果，并调用私有的辅助方法开始递归。
-
辅助方法 (findDepartmentByTypeRecursiveImpl)：
- 遍历当前层级的departments列表。
- 对于每个current部门，首先检查其type是否与目标type匹配。如果匹配，则将其添加到result列表中。
- 接着，判断current是否为Company的实例。如果是，说明它有子部门，需要对其子部门列表再次调用findDepartmentByTypeRecursiveImpl，从而实现深度遍历。
- 递归会一直向下深入，直到遇到叶子部门（没有子部门的Department或Company）或所有子部门都被访问。
优点：
- 代码逻辑清晰，易于理解和实现。
- 与树的自然结构相吻合。
缺点：
- 对于非常深（例如，数千层）的树结构，可能会导致StackOverflowError，因为每次递归调用都会占用Java虚拟机栈的一部分空间。
4. 解决方案二：迭代深度优先搜索 (DFS) 基于栈
为了避免递归可能导致的栈溢出问题，我们可以使用一个显式的栈（java.util.Deque）来模拟递归的调用过程，实现迭代的深度优先搜索。
import java.util.ArrayList;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;
public class OrganizationSearcher {
// ... (同上，包含rootDepartments和构造函数)
/**
* 公开方法：通过迭代方式（使用栈）查找所有指定类型的部门
* @param type 要查找的部门类型
* @return 匹配指定类型的所有部门列表
*/
public List findDepartmentByTypeIterative(String type) {
ArrayList result = new ArrayList<>();
// 使用Deque作为栈，ArrayDeque是推荐的实现
Deque stack = new ArrayDeque<>();
// 将所有根部门压入栈中，作为遍历的起点
if (rootDepartments != null) {
for (Department dept : rootDepartments) {
stack.push(dept); // 使用push将元素压入栈顶
}
}
// 当栈不为空时，持续进行遍历
while (!stack.isEmpty()) {
Department current = stack.pop(); // 弹出栈顶元素进行处理
// 1. 检查当前部门是否匹配
if (type.equals(current.getType())) {
result.add(current);
}
// 2. 如果当前部门是公司，则将其子部门压入栈中
// 注意：为了保持DFS的顺序（通常是先访问左子树再右子树），
// 如果希望子部门按特定顺序处理，压栈时需要注意顺序。
// 这里我们简单地将所有子部门压入，实际遍历顺序可能与递归略有不同，但最终会访问所有节点。
if (current instanceof Company) {
List children = ((Company) current).getDepartments();
if (children != null) {
// 逆序压入子部门，以确保在后续pop时，能够以预期的顺序（例如，与原列表顺序一致）处理
// 或者，如果顺序不重要，直接addAll即可
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}
}
}
return result;
}
} 实现原理：
- 初始化： 创建一个ArrayDeque作为栈，并将所有根部门压入栈中。
-
循环遍历： 当栈不为空时，循环执行以下步骤：
- 弹出元素： 从栈中弹出一个部门current。
- 处理元素： 检查current的type是否匹配。如果匹配，则将其添加到result列表中。
- 压入子元素： 如果current是Company，则获取其所有子部门，并逆序（为了保持DFS的逻辑顺序，即先处理列表中的第一个子部门，后处理最后一个）压入栈中。这样，在下一次循环中，栈顶将是current的第一个子部门，从而实现深度优先。
优点：
- 避免了StackOverflowError，适用于任意深度的树结构。
- 对遍历过程有更精细的控制。
缺点：
- 相对于递归，代码可能稍显复杂，需要手动管理栈。
5. 注意事项与最佳实践
- 类型检查 (instanceof)： 在将Department向下转型为Company之前，务必使用instanceof进行类型检查，以避免ClassCastException。
- 空值处理： 在获取子部门列表或处理根部门列表时，最好进行空值检查（例如if (departments != null)），以增加代码的健壮性。
- 选择合适的栈实现： 在Java中，java.util.Deque接口提供了栈（LIFO）和队列（FIFO）的操作。ArrayDeque是高性能的非线程安全实现，推荐用于单线程环境。LinkedList也可以作为Deque使用，但通常ArrayDeque性能更优。
- 线程安全： 如果OrganizationSearcher实例及其内部的部门结构在多线程环境中被访问，需要确保对rootDepartments和result列表的操作是线程安全的。例如，可以使用Collections.synchronizedList()包装结果列表，或者使用并发集合。
- 性能考量： 对于大多数树结构，递归和迭代的性能差异不大。但对于极端深度的树，迭代方法因避免了Java方法调用栈的开销而更具优势。
6. 总结
在Java中对树形结构进行深度搜索以查找特定元素时，递归和迭代是两种核心且有效的策略。
- 递归方法以其简洁和直观的优点，在树结构问题中广受欢迎。它通过函数自身调用来自然地模拟树的层级关系，但可能受限于调用栈深度。
- 迭代方法则通过显式地管理一个栈来模拟递归过程，从而避免了栈溢出的风险，适用于处理任意深度的树。虽然代码可能略显复杂，但它提供了更强的控制能力和更好的健壮性。
在实际开发中，应根据树的预期深度、代码的可读性偏好以及对性能和内存的特定要求，选择最适合的遍历方法。
