当前位置：首页 > 后端开发 > 正文

Java如何实现树形结构

admin
后端开发
2025-06-14
4202

在Java中实现树形结构通常通过自定义节点类完成，每个节点包含数据及子节点集合（如 List），核心步骤：1. 定义节点类存储数据和子节点引用；2. 递归构建父子关系；3. 通过深度优先或广度优先遍历操作树，也可使用第三方库如Apache Commons Collections简化实现。

树形结构的核心实现方式

基础节点类（多叉树）

import java.util.ArrayList;
import java.util.List;
public class TreeNode<T> {
    private T data; // 节点数据
    private TreeNode<T> parent; // 父节点引用
    private List<TreeNode<T>> children; // 子节点列表
    public TreeNode(T data) {
        this.data = data;
        this.children = new ArrayList<>();
    }
    // 添加子节点
    public void addChild(TreeNode<T> child) {
        child.setParent(this);
        this.children.add(child);
    }
    // 删除子节点
    public void removeChild(TreeNode<T> child) {
        children.remove(child);
        child.setParent(null);
    }
    // Getter & Setter
    public T getData() { return data; }
    public TreeNode<T> getParent() { return parent; }
    public List<TreeNode<T>> getChildren() { return children; }
    private void setParent(TreeNode<T> parent) { this.parent = parent; }
}

二叉树特例实现

public class BinaryTreeNode<T> {
    private T data;
    private BinaryTreeNode<T> left;  // 左子节点
    private BinaryTreeNode<T> right; // 右子节点
    public BinaryTreeNode(T data) {
        this.data = data;
    }
    // 插入左节点
    public void setLeft(BinaryTreeNode<T> node) {
        this.left = node;
    }
    // 插入右节点
    public void setRight(BinaryTreeNode<T> node) {
        this.right = node;
    }
    // Getter & Setter
    public T getData() { return data; }
    public BinaryTreeNode<T> getLeft() { return left; }
    public BinaryTreeNode<T> getRight() { return right; }
}

树形结构的遍历算法

深度优先遍历（DFS）

递归实现（多叉树前序遍历）：

public void dfsTraversal(TreeNode<T> node) {
    if (node == null) return;
    System.out.print(node.getData() + " "); // 操作节点
    for (TreeNode<T> child : node.getChildren()) {
        dfsTraversal(child);
    }
}

广度优先遍历（BFS）

import java.util.LinkedList;
import java.util.Queue;
public void bfsTraversal(TreeNode<T> root) {
    Queue<TreeNode<T>> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode<T> current = queue.poll();
        System.out.print(current.getData() + " "); // 操作节点
        queue.addAll(current.getChildren());
    }
}

实际应用场景与优化

文件系统建模

class FileNode {
    private String name;
    private boolean isDirectory;
    private List<FileNode> children = new ArrayList<>();
    // 构造方法及操作省略...
}

快速父节点回溯

在TreeNode类中添加parent字段,支持从叶子节点快速回溯到根路径：

public List<T> getPathToRoot() {
    List<T> path = new ArrayList<>();
    TreeNode<T> current = this;
    while (current != null) {
        path.add(0, current.getData()); // 添加到头部
        current = current.getParent();
    }
    return path;
}

避免循环引用

在addChild()方法中添加校验：

public void addChild(TreeNode<T> child) {
    if (child == this || isAncestor(child)) {
        throw new IllegalArgumentException("禁止循环引用");
    }
    child.setParent(this);
    children.add(child);
}
private boolean isAncestor(TreeNode<T> node) {
    TreeNode<T> parent = this.parent;
    while (parent != null) {
        if (parent == node) return true;
        parent = parent.getParent();
    }
    return false;
}

高级库与框架推荐

JGraphT（图与树处理）

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-core</artifactId>
    <version>1.5.1</version>
</dependency>

Graph<String, DefaultEdge> tree = new SimpleDirectedGraph<>(DefaultEdge.class);
tree.addVertex("Root");
tree.addVertex("Child");
tree.addEdge("Root", "Child");

Apache Commons Collections

Java如何实现树形结构第1张

Tree<String> tree = new ArrayTree<>("Root");
tree.addNode("Child", "Root");

性能与设计建议

内存优化
- 对大规模静态树使用children数组替代ArrayList
- 二叉树优先使用左右指针而非集合
遍历选择原则
| 场景 | 推荐遍历方式 |
|———————|—————|
| 目录层级展示 | BFS |
| 依赖解析（如Maven） | DFS（后序） |

不可变树
若树结构不变，使用final字段和不可变集合提升线程安全：

private final List<TreeNode<T>> children = Collections.unmodifiableList(new ArrayList<>());

常见问题解决方案

循环引用检测
使用isAncestor()方法（见第三节）或在遍历时记录访问路径。
JSON序列化
使用Gson或Jackson时，通过@JsonIgnore忽略parent字段避免循环：
```
@JsonIgnore
public TreeNode<T> getParent() { 
    return parent; 
}
```
海量数据存储
采用数据库闭包表（Closure Table）结构，
| ancestor | descendant | depth |
|———-|————|——-|
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 1 | 3 | 2 |