Java树结构遍历：按部门类型查找的递归与迭代方法

本文深入探讨了Java中树结构的遍历，重点介绍了如何通过递归和迭代两种方法，在由`Department`和`Company`接口构成的树状组织结构中，高效查找特定类型的部门。针对企业应用中常见的层级数据结构，文章详细阐述了基于深度优先搜索（DFS）的递归实现，以及利用栈模拟DFS的迭代方法，有效避免了递归可能导致的栈溢出问题。通过清晰的代码示例和细致的步骤讲解，帮助Java开发者掌握在复杂树结构中定位目标部门的实用技巧，为构建高效的企业级应用提供参考。掌握这两种遍历策略，能有效处理复杂的层级数据，提升代码的可读性和性能。

本文深入探讨了如何在Java中遍历由Department和Company接口构成的树状结构，以查找特定类型的部门列表。文章详细介绍了两种核心策略：基于递归的深度优先搜索（DFS）实现，以及利用栈进行迭代式遍历的非递归方法。通过代码示例和详细解释，读者将掌握在复杂树结构中高效定位目标元素的技巧。

理解树状结构与业务接口

在许多企业应用中，组织结构常以树的形式呈现。例如，一个公司可能包含多个部门，而某些部门本身又可能是一个更大型的“公司”概念，旗下包含更多子部门。为了模拟这种层级关系，我们定义了两个核心接口：

import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;

public interface Department {
    String getName();
    String getType();

    // 初始尝试中的默认方法，用于匹配单个部门
    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        if (predicate.test(this)) {
            return Optional.of(this);
        }
        return Optional.empty();
    }
}

public interface Company extends Department {
    List<Department> getDepartments();

    // 初始尝试中的默认方法，仅遍历直接子部门
    default Optional<Department> getMatchingDepartment(Predicate<Department> 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）遍历。

实现思路

1. 定义一个公共入口方法，接收要查找的类型，并初始化一个结果列表。
2. 定义一个私有的辅助递归方法，它接收当前要遍历的部门列表、要查找的类型以及用于收集结果的列表。
3. 在辅助方法中，遍历当前部门列表中的每个部门：
   • 如果当前部门的类型与目标类型匹配，则将其添加到结果列表中。
   • 如果当前部门是一个Company实例（即它有子部门），则递归调用辅助方法，传入该Company的子部门列表。

示例代码

import java.util.ArrayList;
import java.util.List;

public class OrganizationSearch {

    // 假设 Concern 类中包含一个根部门列表
    private List<Department> rootDepartments;

    public OrganizationSearch(List<Department> rootDepartments) {
        this.rootDepartments = rootDepartments;
    }

    /**
     * 公共入口方法：通过递归查找所有指定类型的部门。
     * @param type 要查找的部门类型。
     * @return 匹配指定类型的所有部门列表。
     */
    public List<Department> findDepartmentByTypeRecursive(String type) {
        ArrayList<Department> result = new ArrayList<>();
        // 从根部门开始递归遍历
        findDepartmentByTypeRecursiveImpl(type, rootDepartments, result);
        return result;
    }

    /**
     * 私有辅助方法：执行实际的递归遍历逻辑。
     * @param type 要查找的部门类型。
     * @param departments 当前正在遍历的部门列表。
     * @param result 用于收集匹配部门的结果列表。
     */
    private void findDepartmentByTypeRecursiveImpl(String type, List<Department> departments, List<Department> 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虚拟机对栈深度有限制。
• 代码简洁性： 对于树形结构，递归实现通常更符合人类的思维模式，代码逻辑清晰。
• 性能： 在大多数情况下，递归和迭代的性能差异不显著，但递归调用的开销略高于迭代。

迭代实现：使用栈模拟深度优先搜索

为了避免递归可能带来的栈溢出问题，我们可以使用一个显式的数据结构（如栈或队列）来模拟树的遍历过程。对于深度优先搜索，通常使用栈。

实现思路

1. 定义一个公共入口方法，接收要查找的类型，并初始化一个结果列表。
2. 创建一个ArrayList作为栈，并将根部门列表中的所有部门添加到栈中。
3. 进入一个循环，只要栈不为空，就持续执行：
   • 从栈中移除一个部门（通常是最后一个元素，模拟栈的LIFO特性）。
   • 检查该部门的类型是否与目标类型匹配，如果匹配则添加到结果列表中。
   • 如果该部门是一个Company实例，则将其所有子部门添加到栈中，以便后续处理。

示例代码

import java.util.ArrayList;
import java.util.List;

public class OrganizationSearch {

    private List<Department> rootDepartments;

    public OrganizationSearch(List<Department> rootDepartments) {
        this.rootDepartments = rootDepartments;
    }

    /**
     * 公共入口方法：通过迭代查找所有指定类型的部门。
     * @param type 要查找的部门类型。
     * @return 匹配指定类型的所有部门列表。
     */
    public List<Department> findDepartmentByTypeIterative(String type) {
        ArrayList<Department> result = new ArrayList<>();
        // 使用ArrayList模拟栈，存储待处理的部门
        ArrayList<Department> 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<Department> 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中遍历树状结构并查找特定类型的元素，可以采用递归或迭代两种主要方法。递归方法简洁直观，适用于大多数情况，但需注意栈溢出风险。迭代方法通过显式使用栈（或队列）来模拟遍历过程，能够有效避免栈溢出问题，适用于处理深度较大的树结构。选择哪种方法取决于具体的场景需求、树的深度以及对代码可读性和性能的要求。在实际开发中，理解并掌握这两种遍历策略对于处理复杂的层级数据至关重要。

到这里，我们也就讲完了《Java树结构遍历：按部门类型查找的递归与迭代方法》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！