用 Java 流的方式实现树型结构

在Java中，流（Stream）是一种处理集合数据的高级抽象，它提供了一种优雅且功能强大的方式来处理集合。当我们面对树型结构时，例如树（Tree）或图（Graph），使用流的方式可以使代码更为清晰、简洁，同时充分发挥Java 8引入的函数式编程特性。

下面将详细讲述一下如何利用Java流的方式来实现树型结构。

1. 树的节点定义

首先，我们需要定义树的节点。每个节点通常包含一个数据元素和指向其子节点的引用。我们使用一个简单的节点类来表示树的基本结构：

class TreeNode<T> {
    private T data;
    private List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new ArrayList<>();
    }

    public T getData() {
        return data;
    }

    public List<TreeNode<T>> getChildren() {
        return children;
    }

    public void addChild(TreeNode<T> child) {
        children.add(child);
    }
}

在这个类中，TreeNode 包含了一个泛型类型的数据元素和一个子节点列表。通过addChild方法，我们可以方便地向节点添加子节点。

2. 构建树结构

现在，我们来构建一个简单的树结构。假设我们要创建一个表示文件系统的树，其中每个节点表示一个目录，并包含其子目录和文件。我们可以按照如下方式构建这个树：

// 构建文件系统树
TreeNode<String> root = new TreeNode<>("root");

TreeNode<String> documents = new TreeNode<>("Documents");
documents.addChild(new TreeNode<>("Resume.docx"));
documents.addChild(new TreeNode<>("Reports"));

TreeNode<String> pictures = new TreeNode<>("Pictures");
pictures.addChild(new TreeNode<>("Vacation.jpg"));
pictures.addChild(new TreeNode<>("Family"));

root.addChild(documents);
root.addChild(pictures);

这样，我们就创建了一个包含根目录、文档目录和图片目录的简单文件系统树。

3. 使用流遍历树

接下来，我们将使用Java流的方式来遍历这个树。首先，我们可以使用递归方式实现深度优先遍历：

// 深度优先遍历
public static <T> Stream<TreeNode<T>> flattenTree(TreeNode<T> root) {
    return Stream.concat(
            Stream.of(root),
            root.getChildren().stream().flatMap(TreeExample::flattenTree)
    );
}

// 示例用法
flattenTree(root)
    .forEach(node -> System.out.println(node.getData()));

上述代码中，flattenTree 方法通过递归地将当前节点和其子节点展平为一个流。然后，我们使用 forEach 方法遍历流中的每个节点并打印其数据。

除了深度优先遍历，我们还可以实现宽度优先遍历：

// 宽度优先遍历
public static <T> Stream<TreeNode<T>> breadthFirstTraversal(TreeNode<T> root) {
    Queue<TreeNode<T>> queue = new LinkedList<>();
    queue.add(root);

    return Stream.generate(() -> {
        TreeNode<T> node = queue.poll();
        if (node != null) {
            queue.addAll(node.getChildren());
        }
        return node;
    }).takeWhile(Objects::nonNull);
}

// 示例用法
breadthFirstTraversal(root)
    .forEach(node -> System.out.println(node.getData()));

在这个例子中，breadthFirstTraversal 方法使用队列来实现宽度优先遍历。我们使用 generate 方法创建一个无限流，每次从队列中取出一个节点，并将其子节点加入队列。通过 takeWhile 方法，我们可以在流中保留非空节点。

4. 过滤和转换

使用流的方式，我们可以方便地进行过滤和转换操作。例如，假设我们要找到所有文件的节点，可以使用 filter 操作：

// 找到所有文件节点
List<TreeNode<String>> files = flattenTree(root)
    .filter(node -> node.getData().contains("."))
    .collect(Collectors.toList());

上述代码中，我们通过 filter 方法筛选出包含点（.）的节点，即文件节点，并使用 collect 方法将结果收集到一个列表中。

同样，我们可以使用 map 操作进行节点数据的转换。例如，将所有文件节点的数据转换为大写：

// 转换所有文件节点的数据为大写
List<String> upperCaseFileNames = files.stream()
    .map(node -> node.getData().toUpperCase())
    .collect(Collectors.toList());

5. 递归操作

在处理树型结构时，有时我们需要对每个节点及其子节点执行某个操作。这可以通过递归和流的方式实现。例如，假设我们要计算树的深度：

// 计算树的深度
public static <T> int calculateDepth(TreeNode<T> node) {
    return node.getChildren().stream()
        .map(TreeExample::calculateDepth)
        .max(Integer::compare)
        .orElse(0) + 1;
}

// 示例用法
int depth = calculateDepth(root);
System.out.println("Tree Depth: " + depth);

在这个例子中，calculateDepth 方法递归地计算每个子树的深度，并返回最大深度加一。通过使用流的 map 操作和 max 操作，我们可以方便地对每个子树的深度进行比较和聚合。

6. 并行流

Java流支持并行操作，这意味着我们可以轻松地将流操作转换为并行操作以提高性能。在树型结构中，这对于对多个子树进行独立操作的场景非常有用。

// 并行深度优先遍历
flattenTree(root).parallel()
    .forEach(node -> System.out.println(Thread.currentThread().getName() + ": " + node.getData()));

在这个例子中，通过 parallel 方法将流转换为并行流，使得深度优先遍历可以并行进行。并行流的使用需要注意线程安全性，确保在并行执行的情况下，对共享数据的访问是安全的。

7. 自定义操作

流的方式允许我们定义自己的操作，以满足特定需求。例如，假设我们想要查找树中是否存在某个特定的节点：

// 查找节点
public static <T> Optional<TreeNode<T>> findNode(TreeNode<T> root, T target) {
    return flattenTree(root)
        .filter(node -> node.getData().equals(target))
        .findFirst();
}

// 示例用法
String targetNodeData = "Reports";
findNode(root, targetNodeData)
    .ifPresent(node -> System.out.println("Node found: " + node.getData()));

在这个例子中，findNode 方法使用流的 filter 操作查找数据与目标值相等的节点，并使用 findFirst 获取第一个匹配的节点。这种自定义操作可以根据具体需求随意扩展。

8. 最后

使用Java流的方式来处理树型结构可以使代码更为清晰、简洁，同时充分发挥Java 8引入的函数式编程特性。通过深度优先遍历、宽度优先遍历以及各种过滤、转换和自定义操作，我们可以轻松地操作和处理树中的节点。并行流的使用还可以提高处理性能，特别是在大规模树结构的情况下。

当处理树型结构时，注意保持数据的一致性和线程安全性是非常重要的。确保在并行操作中，对共享数据的访问是安全的，并且对于可变状态的节点，需要采取适当的同步措施。

总的来说，使用Java流的方式处理树型结构是一种优雅而强大的编程范式，可以提高代码的可读性和可维护性。

黑马程序员Java零基础视频教程_上部(Java入门，含斯坦福大学练习题+力扣算法题和大厂java面试题）

黑马程序员Java零基础视频教程_下部(Java入门，含斯坦福大学练习题+力扣算法题和大厂java面试题）