Java 树形结构

1. 介绍

树是一种常见的数据结构，它由节点和边组成，节点之间的连接以一种层次化的方式进行。每个节点可以有零个或多个子节点，但每个节点只能有一个父节点。

在 Java 中，树形结构可以用来表示和组织数据，例如文件系统、目录结构、组织架构等。本文将详细介绍如何使用 Java 实现树形结构，并提供示例代码演示。

2. 树的基本概念

在开始实现树形结构之前，我们先来了解一些树的基本概念。

节点（Node）：树的基本单元，包含一个数据项和指向子节点的指针。
根节点（Root Node）：没有父节点的节点，树的入口点。
叶子节点（Leaf Node）：没有子节点的节点。
父节点（Parent Node）：有子节点的节点。
子节点（Child Node）：父节点的直接下级节点。
兄弟节点（Sibling Node）：具有共同父节点的节点。
路径（Path）：从根节点到叶子节点的所有节点。
层次（Level）：根节点的层次为 0，根节点的子节点为第一层，以此类推。
深度（Depth）：树的最大层次数。
度（Degree）：节点拥有的子节点数目。
高度（Height）：从叶子节点到某个节点的最长路径。

3. Java 实现树的基本结构

在 Java 中，我们可以通过自定义类来实现树的基本结构。每个节点可以用一个类来表示，该类可以包含数据项和子节点的引用。

下面是一个简单的 Java 类来表示树的节点：

class TreeNode<E> {
    private E data; // 数据项
    private List<TreeNode<E>> children; // 子节点列表

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

    // ... 省略了一些其他方法
}

在上面的代码中，我们使用了泛型来支持任意类型的数据项。TreeNode 类有一个私有的数据项 data，用于存储节点的数据。children 是一个 List，用于存储节点的子节点。

为了方便起见，我们还提供了一个构造方法来创建一个带有数据项的节点。

4. 添加子节点和获取子节点

要实现一个树形结构，我们需要能够添加子节点和获取子节点。下面是 TreeNode 类中的两个方法来实现这个功能：

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

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

上面的代码中，addChild 方法用于添加一个子节点到当前节点的子节点列表中。getChildren 方法用于获取当前节点的子节点列表。

5. 遍历树

树是由节点和边组成的，我们可以通过遍历树的节点来处理树的数据。在树的遍历中，有两种常用的方法：深度优先遍历和广度优先遍历。

5.1 深度优先遍历

深度优先遍历（Depth First Traversal）是一种沿着树的深度遍历的方法，当遍历到一个节点时，首先访问该节点，然后递归遍历它的子节点。

下面是一个递归实现的深度优先遍历树的示例代码：

public void depthFirstTraversal(TreeNode<E> root) {
    if (root == null) {
        return;
    }

    System.out.println(root.getData());

    for (TreeNode<E> child : root.getChildren()) {
        depthFirstTraversal(child);
    }
}

在上面的代码中，depthFirstTraversal 方法接受一个树的根节点作为参数。如果根节点为空，则直接返回。否则，首先访问根节点的数据，然后遍历根节点的子节点，并递归调用 depthFirstTraversal 方法。

5.2 广度优先遍历

广度优先遍历（Breadth First Traversal）是一种一层一层地遍历树的节点，首先访问根节点，然后依次访问根节点的各个子节点。

下面是一个使用队列实现的广度优先遍历树的示例代码：

public void breadthFirstTraversal(TreeNode<E> root) {
    if (root == null) {
        return;
    }

    Queue<TreeNode<E>> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode<E> node = queue.poll();

        System.out.println(node.getData());

        for (TreeNode<E> child : node.getChildren()) {
            queue.add(child);
        }
    }
}

在上面的代码中，breadthFirstTraversal 方法接受一个树的根节点作为参数。如果根节点为空，则直接返回。否则，创建一个队列，并将根节点入队列。然后，循环处理队列中的节点，首先访问节点的数据，并将节点的子节点入队列。

6. 示例

下面是一个使用树形结构实现文件系统的示例代码：

public class File {
    private String name;
    private List<File> children;

    public File(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

    public void addChild(File child) {
        children.add(child);
    }

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

    // ... 省略了一些其他方法

    public static void main(String[] args) {
        File root = new File("root");
        File documents = new File("documents");
        File pictures = new File("pictures");
        File music = new File("music");

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

        File text = new File("text.txt");
        File image = new File("image.png");
        File song = new File("song.mp3");

        documents.addChild(text);
        pictures.addChild(image);
        music.addChild(song);

        root.depthFirstTraversal(root); // 深度优先遍历
        root.breadthFirstTraversal(root); // 广度优先遍历
    }
}

上面的代码中，我们模拟了一个简单的文件系统，包含根目录和三个子目录。然后，我们将树形结构通过深度优先遍历和广度优先遍历进行打印。