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

Java如何实现树形结构

admin
后端开发
2025-06-14
6

在 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
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 |