Java 树形结构深度搜索与部门查找实践-java教程-PHP中文网

Java 树形结构深度搜索与部门查找实践

本文深入探讨了在Java中遍历树形结构以查找特定类型部门的两种核心方法：递归与迭代。通过定义Department和Company接口构建树状层级，文章详细阐述了如何利用这两种策略高效地实现深度优先搜索，从而解决在复杂组织结构中按类型筛选部门的实际问题，并提供了清晰的代码示例与专业指导。

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<Department> getMatchingDepartment(Predicate<Department> predicate) {
        if (predicate.test(this)) {
            return Optional.of(this);
        }
        return Optional.empty();
    }
}

登录后复制

/**
 * 公司接口，继承自Department，并表示一个可以包含子部门的实体。
 * 它构成了树形结构中的内部节点。
 */
public interface Company extends Department {
    List<Department> getDepartments(); // 获取当前公司下的所有子部门

    /**
     * 默认方法：尝试查找当前公司直接子部门中第一个匹配谓词的部门。
     * 注意：此方法仅遍历直接子部门，不进行深度递归。
     * @param predicate 用于测试部门的条件
     * @return 如果找到匹配的直接子部门则返回包含该部门的Optional，否则返回空的Optional
     */
    default Optional<Department> getMatchingDepartment(Predicate<Department> 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<Department> rootDepartments; // 假设这是整个组织的顶层部门列表

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

    /**
     * 根据部门类型查找所有匹配的部门（递归实现）。
     *
     * @param type 要查找的部门类型
     * @return 匹配指定类型的所有部门列表
     */
    public List<Department> findDepartmentByType(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) {
            // 1. 检查当前部门是否匹配类型
            if (type.equals(current.getType())) {
                result.add(current);
            }
            // 2. 如果当前部门是公司类型，则递归遍历其子部门
            if (current instanceof Company) {
                findDepartmentByTypeRecursiveImpl(type, ((Company) current).getDepartments(), result);
            }
        }
    }

    // 以下是原始问题中提供的其他查找方法，为保持上下文完整性保留
    public Optional<Department> findDepartmentByName(String name) {
        return findDepartmentByPredicate(department -> department.getName().equals(name)).findFirst();
    }

    private Stream<Department> findDepartmentByPredicate(Predicate<Department> 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）时，递归路径自然结束。

注意事项：

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

递归深度过大可能导致栈溢出（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<Department> rootDepartments;

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

    /**
     * 根据部门类型查找所有匹配的部门（迭代实现）。
     *
     * @param type 要查找的部门类型
     * @return 匹配指定类型的所有部门列表
     */
    public List<Department> findDepartmentByTypeIterative(String type) {
        ArrayList<Department> result = new ArrayList<>();
        Stack<Department> 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<Department> 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的第一个子部门，从而实现深度优先的遍历顺序。

注意事项：