引言：树结构在软件开发中的核心地位
树结构是计算机科学中最基础且最重要的数据结构之一，它在现实世界中有着广泛的应用场景。在Java开发中，树结构的构建和操作是许多高级算法和系统设计的基础。无论是文件系统的目录结构、组织架构的层级关系、还是电商商品的分类体系，都离不开树结构的支持。
本文将从零基础开始，系统地讲解如何在Java中构建树结构，涵盖递归和非递归两种核心实现方式，并通过详细的案例分析和性能优化技巧，帮助读者从入门到精通。
1. 树结构基础概念
1.1 什么是树结构
树结构是由节点（Node）组成的层级数据结构，具有以下特点：
每个节点最多有一个父节点
除了根节点外，每个节点有且仅有一个父节点
节点之间不能形成环
树结构天然支持层级关系的表示
1.2 树结构的常见类型
普通树
：最基础的树结构，节点可以有任意数量的子节点
二叉树
：每个节点最多有两个子节点（左子节点和右子节点）
二叉搜索树
：满足特定排序规则的二叉树
平衡树
：通过特定算法保持树的平衡性，如AVL树、红黑树
多叉树
：节点可以有多个子节点，常用于表示层级关系
1.3 树结构的应用场景
文件系统
：目录和文件的层级关系
组织架构
：公司部门和员工的层级关系
商品分类
：电商平台上商品的分类体系
DOM树
：网页元素的层级结构
语法树
：编译器中的抽象语法树
2. Java中树节点的定义
在Java中，我们首先需要定义树节点的数据结构。根据不同的需求，节点可以有不同的实现方式。
2.1 基础树节点定义
/**
* 基础树节点类
* @param
*/
public class TreeNode
private T data; // 节点数据
private List
private TreeNode
public TreeNode(T data) {
this.data = data;
this.children = new ArrayList<>();
}
// Getter和Setter方法
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public List
return children;
}
public void setChildren(List
this.children = children;
}
public TreeNode
return parent;
}
public void setParent(TreeNode
this.parent = parent;
}
/**
* 添加子节点
*/
public void addChild(TreeNode
this.children.add(child);
child.setParent(this);
}
/**
* 移除子节点
*/
public boolean removeChild(TreeNode
boolean removed = this.children.remove(child);
if (removed) {
child.setParent(null);
}
return removed;
}
/**
* 判断是否为叶子节点
*/
public boolean isLeaf() {
return this.children.isEmpty();
}
/**
* 获取节点深度（到根节点的距离）
*/
public int getDepth() {
int depth = 0;
TreeNode
while (current.parent != null) {
depth++;
current = current.parent;
}
return depth;
}
@Override
public String toString() {
return “TreeNode{” +
“data=” + data +
“, children=” + children.size() +
‘}’;
}
}
2.2 业务场景下的树节点定义
在实际业务中，我们通常需要根据具体的业务需求来定义节点。例如，一个表示组织架构的节点：
/**
* 组织架构节点
*/
public class OrgNode {
private String id; // 部门/员工ID
private String name; // 部门/员工名称
private String parentId; // 父级ID
private List
public OrgNode(String id, String name, String parentId) {
this.id = id;
this.name = name;
this.parentId = parentId;
this.children = new ArrayList<>();
}
// Getter和Setter方法
public String getId() { return id; }
public void setId(String id) { this.id = id; }
public String getName() { return name; }
public void setName(String name) { this.name = name; }
public String getParentId() { return parentId; }
public void setParentId(String parentId) { this.parentId = parentId; }
public List
public void setChildren(List
/**
* 添加子节点
*/
public void addChild(OrgNode child) {
this.children.add(child);
}
@Override
public String toString() {
return “OrgNode{” +
“id=’” + id + ‘\” +
“, name=’” + name + ‘\” +
“, children=” + children.size() +
‘}’;
}
}
3. 递归算法构建树结构
递归是构建树结构最直观、最常用的方法。递归算法代码简洁，易于理解，但在处理大规模数据时可能存在性能问题。
3.1 递归构建树的基本原理
递归构建树的核心思想是：
找到根节点（没有父节点的节点）
为每个节点递归地查找并添加其子节点
递归终止条件：节点没有子节点
3.2 从扁平列表递归构建树
假设我们有一个包含节点信息的列表，每个节点包含ID和父ID：
import java.util.*;
import java.util.stream.Collectors;
/**
* 递归方式构建树结构
*/
public class RecursiveTreeBuilder {
/**
* 从扁平列表递归构建树
* @param nodeList 节点列表
* @return 树的根节点列表
*/
public static List
if (nodeList == null || nodeList.isEmpty()) {
return new ArrayList<>();
}
// 1. 创建ID到节点的映射，便于快速查找
Map
for (OrgNode node : nodeList) {
nodeMap.put(node.getId(), node);
}
// 2. 找出所有根节点（parentId为空或null）
List
.filter(node -> node.getParentId() == null ||
node.getParentId().isEmpty() ||
!nodeMap.containsKey(node.getParentId()))
.collect(Collectors.toList());
// 3. 递归构建子树
for (OrgNode node : nodeList) {
if (node.getParentId() != null && !node.getParentId().isEmpty()) {
OrgNode parent = nodeMap.get(node.getParentId());
if (parent != null) {
parent.addChild(node);
}
}
}
return rootNodes;
}
/**
* 递归方式查找节点的所有子节点（深度优先）
* @param node 当前节点
* @param depth 当前深度（用于缩进显示）
*/
public static void printTreeRecursive(OrgNode node, int depth) {
if (node == null) return;
// 打印当前节点（使用缩进表示层级）
String indent = ” “.repeat(depth);
System.out.println(indent + node.getName() + ” (ID: ” + node.getId() + “)”);
// 递归打印所有子节点
for (OrgNode child : node.getChildren()) {
printTreeRecursive(child, depth + 1);
}
}
/**
* 递归计算树的深度
*/
public static int calculateTreeDepth(OrgNode node) {
if (node == null || node.getChildren().isEmpty()) {
return 0;
}
int maxChildDepth = 0;
for (OrgNode child : node.getChildren()) {
int childDepth = calculateTreeDepth(child);
maxChildDepth = Math.max(maxChildDepth, childDepth);
}
return maxChildDepth + 1;
}
/**
* 递归查找节点
*/
public static OrgNode findNodeRecursive(OrgNode root, String id) {
if (root == null) return null;
if (root.getId().equals(id)) return root;
for (OrgNode child : root.getChildren()) {
OrgNode found = findNodeRecursive(child, id);
if (found != null) return found;
}
return null;
}
}
3.3 递归构建树的完整示例
public class RecursiveTreeExample {
public static void main(String[] args) {
// 1. 创建测试数据
List
nodeList.add(new OrgNode(“1”, “总公司”, null));
nodeList.add(new OrgNode(“2”, “技术部”, “1”));
nodeList.add(new OrgNode(“3”, “市场部”, “1”));
nodeList.add(new OrgNode(“4”, “研发组”, “2”));
nodeList.add(new OrgNode(“5”, “测试组”, “2”));
nodeList.add(new OrgNode(“6”, “销售组”, “3”));
nodeList.add(new OrgNode(“7”, “张三”, “4”));
nodeList.add(new OrgNode(“8”, “李四”, “4”));
nodeList.add(new OrgNode(“9”, “王五”, “5”));
// 2. 构建树结构
List
// 3. 打印树结构
System.out.println(“=== 递归构建的树结构 ===”);
for (OrgNode root : tree) {
RecursiveTreeBuilder.printTreeRecursive(root, 0);
}
// 4. 计算树的深度
int depth = RecursiveTreeBuilder.calculateTreeDepth(tree.get(0));
System.out.println(“\n树的深度: ” + depth);
// 5. 查找节点
OrgNode found = RecursiveTreeBuilder.findNodeRecursive(tree.get(0), “5”);
System.out.println(“查找节点ID=5: ” + (found != null ? found.getName() : “未找到”));
}
}
运行结果：
=== 递归构建的树结构 ===
总公司 (ID: 1)
技术部 (ID: 2)
研发组 (ID: 4)
张三 (ID: 7)
李四 (ID: 8)
测试组 (ID: 5)
王五 (ID: 9)
市场部 (ID: 3)
销售组 (ID: 6)
树的深度: 3
查找节点ID=5: 测试组
3.4 递归算法的优缺点分析
优点：
代码简洁，逻辑清晰
符合树结构的自然定义
易于理解和维护
缺点：
处理大规模数据时可能导致栈溢出
重复计算问题，效率相对较低
难以进行优化和并行处理
4. 非递归高效实现
非递归实现通常使用栈或队列等数据结构来模拟递归过程，可以避免栈溢出问题，并且在某些场景下性能更优。
4.1 使用栈实现深度优先遍历（DFS）
import java.util.*;
/**
* 非递归方式构建和遍历树
*/
public class NonRecursiveTreeBuilder {
/**
* 非递归方式构建树（使用Map缓存）
* @param nodeList 节点列表
* @return 树的根节点列表
*/
public static List
if (nodeList == null || nodeList.isEmpty()) {
return new ArrayList<>();
}
// 1. 创建ID到节点的映射
Map
for (OrgNode node : nodeList) {
nodeMap.put(node.getId(), node);
}
// 2. 找出所有根节点
List
Set
// 收集所有父节点ID
for (OrgNode node : nodeList) {
if (node.getParentId() != null && !node.getParentId().isEmpty()) {
parentIds.add(node.getParentId());
}
}
// 找出根节点（没有父节点的节点）
for (OrgNode node : nodeList) {
if (!parentIds.contains(node.getId())) {
rootNodes.add(node);
}
}
// 3. 非递归构建子节点关系
for (OrgNode node : nodeList) {
if (node.getParentId() != null && !node.getParentId().isEmpty()) {
OrgNode parent = nodeMap.get(node.getParentId());
if (parent != null) {
parent.addChild(node);
}
}
}
return rootNodes;
}
/**
* 非递归方式遍历树（使用栈实现DFS）
*/
public static void printTreeDFS(OrgNode root) {
if (root == null) return;
// 使用栈来存储待访问的节点和对应的深度
Stack
Stack
stack.push(root);
depthStack.push(0);
while (!stack.isEmpty()) {
OrgNode current = stack.pop();
int depth = depthStack.pop();
// 打印当前节点
String indent = ” “.repeat(depth);
System.out.println(indent + current.getName() + ” (ID: ” + current.getId() + “)”);
// 将子节点压入栈（注意顺序，需要逆序压入以保持正确的遍历顺序）
List
for (int i = children.size() – 1; i >= 0; i–) {
stack.push(children.get(i));
depthStack.push(depth + 1);
}
}
}
/**
* 非递归方式遍历树（使用队列实现BFS – 层级遍历）
*/
public static void printTreeBFS(OrgNode root) {
if (root == null) return;
// 使用队列实现广度优先遍历
Queue
Queue
queue.offer(root);
depthQueue.offer(0);
while (!queue.isEmpty()) {
OrgNode current = queue.poll();
int depth = depthQueue.poll();
// 打印当前节点
String indent = ” “.repeat(depth);
System.out.println(indent + current.getName() + ” (ID: ” + current.getId() + “)”);
// 将子节点加入队列
for (OrgNode child : current.getChildren()) {
queue.offer(child);
depthQueue.offer(depth + 1);
}
}
}
/**
* 非递归查找节点（DFS）
*/
public static OrgNode findNodeNonRecursive(OrgNode root, String id) {
if (root == null) return null;
Stack
stack.push(root);
while (!stack.isEmpty()) {
OrgNode current = stack.pop();
if (current.getId().equals(id)) {
return current;
}
// 将子节点压入栈
for (OrgNode child : current.getChildren()) {
stack.push(child);
}
}
return null;
}
/**
* 非递归计算树的深度（使用BFS）
*/
public static int calculateTreeDepthNonRecursive(OrgNode root) {
if (root == null) return 0;
Queue
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
// 处理当前层级的所有节点
for (int i = 0; i < levelSize; i++) {
OrgNode current = queue.poll();
// 将子节点加入队列
for (OrgNode child : current.getChildren()) {
queue.offer(child);
}
}
depth++;
}
return depth;
}
}
4.2 非递归实现的完整示例
public class NonRecursiveTreeExample {
public static void main(String[] args) {
// 1. 创建测试数据
List
nodeList.add(new OrgNode(“1”, “总公司”, null));
nodeList.add(new OrgNode(“2”, “技术部”, “1”));
nodeList.add(new OrgNode(“3”, “市场部”, “1”));
nodeList.add(new OrgNode(“4”, “研发组”, “2”));
nodeList.add(new OrgNode(“5”, “测试组”, “2”));
nodeList.add(new OrgNode(“6”, “销售组”, “3”));
nodeList.add(new OrgNode(“7”, “张三”, “4”));
nodeList.add(new OrgNode(“8”, “李四”, “4”));
nodeList.add(new OrgNode(“9”, “王五”, “5”));
// 2. 非递归构建树
List
// 3. DFS遍历
System.out.println(“=== 非递归DFS遍历 ===”);
for (OrgNode root : tree) {
NonRecursiveTreeBuilder.printTreeDFS(root);
}
// 4. BFS遍历
System.out.println(“\n=== 非递归BFS遍历 ===”);
for (OrgNode root : tree) {
NonRecursiveTreeBuilder.printTreeBFS(root);
}
// 5. 计算深度
int depth = NonRecursiveTreeBuilder.calculateTreeDepthNonRecursive(tree.get(0));
System.out.println(“\n树的深度: ” + depth);
// 6. 查找节点
OrgNode found = NonRecursiveTreeBuilder.findNodeNonRecursive(tree.get(0), “5”);
System.out.println(“查找节点ID=5: ” + (found != null ? found.getName() : “未找到”));
}
}
4.3 非递归算法的优缺点分析
优点：
避免栈溢出，适合处理大规模数据
性能通常优于递归实现
可以更好地控制遍历过程
易于并行化和优化
缺点：
代码相对复杂，理解难度较高
需要额外的数据结构（栈/队列）存储状态
内存占用相对较高
5. 性能优化技巧
5.1 优化数据结构选择
/**
* 优化的树节点定义
*/
public class OptimizedTreeNode {
private String id;
private String name;
private String parentId;
private List
private OptimizedTreeNode parent;
// 使用ArrayList的初始容量优化
public OptimizedTreeNode(String id, String name, String parentId) {
this.id = id;
this.name = name;
this.parentId = parentId;
this.children = new ArrayList<>(8); // 预分配容量，减少扩容开销
}
// 其他方法…
}
5.2 使用缓存优化重复查询
/**
* 带缓存的树结构管理器
*/
public class CachedTreeManager {
private final Map
private final Map
private List
/**
* 构建树并缓存结果
*/
public void buildTree(List
// 清空缓存
nodeCache.clear();
childrenCache.clear();
// 构建节点映射
Map
for (OrgNode node : nodeList) {
nodeCache.put(node.getId(), node);
if (node.getParentId() != null && !node.getParentId().isEmpty()) {
parentToChildrenMap.computeIfAbsent(node.getParentId(), k -> new ArrayList<>())
.add(node);
}
}
// 构建树结构
rootNodes = new ArrayList<>();
Set
// 收集所有子节点ID
parentToChildrenMap.values().forEach(children -> {
for (OrgNode child : children) {
childIds.add(child.getId());
}
});
// 找出根节点
for (OrgNode node : nodeList) {
if (!childIds.contains(node.getId())) {
rootNodes.add(node);
}
}
// 递归构建并缓存子节点列表
for (OrgNode root : rootNodes) {
buildChildrenCache(root, parentToChildrenMap);
}
}
/**
* 递归构建子节点缓存
*/
private void buildChildrenCache(OrgNode node, Map
List
node.setChildren(children);
childrenCache.put(node.getId(), children);
for (OrgNode child : children) {
buildChildrenCache(child, parentToChildrenMap);
}
}
/**
* 快速查找节点（使用缓存）
*/
public OrgNode findNode(String id) {
return nodeCache.get(id);
}
/**
* 快速获取子节点（使用缓存）
*/
public List
return childrenCache.getOrDefault(parentId, new ArrayList<>());
}
/**
* 快速获取所有后代节点
*/
public List
List
Queue
queue.offer(nodeId);
while (!queue.isEmpty()) {
String currentId = queue.poll();
List
for (OrgNode child : children) {
descendants.add(child);
queue.offer(child.getId());
}
}
return descendants;
}
}
5.3 并行构建优化
import java.util.concurrent.*;
/**
* 并行构建树结构
*/
public class ParallelTreeBuilder {
/**
* 并行构建树结构（适用于大规模数据）
*/
public static List
if (nodeList == null || nodeList.isEmpty()) {
return new ArrayList<>();
}
// 1. 创建节点映射（并行流优化）
Map
.collect(Collectors.toMap(OrgNode::getId, node -> node));
// 2. 分区处理：根节点和子节点
CompletableFuture
// 3. 并行查找根节点
CompletableFuture
Set
.filter(node -> node.getParentId() != null)
.map(OrgNode::getParentId)
.collect(Collectors.toSet());
return nodeList.parallelStream()
.filter(node -> !parentIds.contains(node.getId()))
.collect(Collectors.toList());
});
// 4. 等待所有任务完成
Map
List
// 5. 并行构建子节点关系
nodeList.parallelStream()
.filter(node -> node.getParentId() != null && !node.getParentId().isEmpty())
.forEach(node -> {
OrgNode parent = completedNodeMap.get(node.getParentId());
if (parent != null) {
synchronized (parent) {
parent.addChild(node);
}
}
});
return rootNodes;
}
}
5.4 内存优化技巧
/**
* 内存优化的树结构
*/
public class MemoryOptimizedTree {
/**
* 使用数组存储子节点（适用于子节点数量固定且较少的场景）
*/
static class ArrayTreeNode {
private String id;
private String name;
private ArrayTreeNode[] children;
private int childCount = 0;
public ArrayTreeNode(String id, String name, int maxChildren) {
this.id = id;
this.name = name;
this.children = new ArrayTreeNode[maxChildren];
}
public boolean addChild(ArrayTreeNode child) {
if (childCount < children.length) {
children[childCount++] = child;
return true;
}
return false;
}
public ArrayTreeNode[] getChildren() {
return Arrays.copyOf(children, childCount);
}
}
/**
* 使用位图优化存储（适用于节点ID是连续整数的场景）
*/
static class BitMapTree {
private BitSet parentMap; // 使用位图记录父子关系
private int maxId;
public BitMapTree(int maxId) {
this.maxId = maxId;
this.parentMap = new BitSet(maxId * maxId); // 简化示例
}
public void setParent(int childId, int parentId) {
int index = childId * maxId + parentId;
parentMap.set(index);
}
public boolean hasParent(int childId, int parentId) {
int index = childId * maxId + parentId;
return parentMap.get(index);
}
}
}
6. 案例分析：实际业务场景应用
6.1 案例1：电商商品分类树
/**
* 电商商品分类树实现
*/
public class ProductCategoryTree {
/**
* 商品分类节点
*/
static class CategoryNode {
private Long id;
private String name;
private Long parentId;
private List
private int productCount; // 该分类下的商品数量
public CategoryNode(Long id, String name, Long parentId) {
this.id = id;
this.name = name;
this.parentId = parentId;
this.children = new ArrayList<>();
this.productCount = 0;
}
// Getter和Setter方法…
public Long getId() { return id; }
public String getName() { return name; }
public Long getParentId() { return parentId; }
public List
public int getProductCount() { return productCount; }
public void setProductCount(int productCount) { this.productCount = productCount; }
public void addChild(CategoryNode child) {
this.children.add(child);
}
}
private List
private Map
/**
* 从数据库查询结果构建分类树
*/
public void buildFromDatabase(List
this.categoryMap = new HashMap<>();
// 构建映射
for (CategoryNode category : categories) {
categoryMap.put(category.getId(), category);
}
// 构建树结构
this.rootCategories = new ArrayList<>();
for (CategoryNode category : categories) {
if (category.getParentId() == null || category.getParentId() == 0) {
rootCategories.add(category);
} else {
CategoryNode parent = categoryMap.get(category.getParentId());
if (parent != null) {
parent.addChild(category);
}
}
}
// 计算每个分类的商品数量（递归）
for (CategoryNode root : rootCategories) {
calculateProductCount(root);
}
}
/**
* 递归计算商品数量
*/
private int calculateProductCount(CategoryNode node) {
int count = node.getProductCount(); // 该分类自身的商品数
for (CategoryNode child : node.getChildren()) {
count += calculateProductCount(child);
}
// 更新节点的商品数量（包含子分类）
node.setProductCount(count);
return count;
}
/**
* 获取分类路径（从根到当前节点）
*/
public List
List
CategoryNode current = categoryMap.get(categoryId);
if (current == null) return path;
while (current != null) {
path.add(0, current); // 添加到头部，保持从根到当前的顺序
current = categoryMap.get(current.getParentId());
}
return path;
}
/**
* 获取指定层级的分类
*/
public List
List
Queue
for (CategoryNode root : rootCategories) {
queue.offer(root);
}
int currentLevel = 0;
while (!queue.isEmpty() && currentLevel < level) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
CategoryNode current = queue.poll();
queue.addAll(current.getChildren());
}
currentLevel++;
}
if (currentLevel == level) {
result.addAll(queue);
}
return result;
}
/**
* 搜索分类（模糊匹配名称）
*/
public List
List
for (CategoryNode root : rootCategories) {
searchRecursive(root, keyword, results);
}
return results;
}
private void searchRecursive(CategoryNode node, String keyword, List
if (node.getName().toLowerCase().contains(keyword.toLowerCase())) {
results.add(node);
}
for (CategoryNode child : node.getChildren()) {
searchRecursive(child, keyword, results);
}
}
/**
* 打印分类树（带商品数量统计）
*/
public void printCategoryTree() {
for (CategoryNode root : rootCategories) {
printCategoryNode(root, 0);
}
}
private void printCategoryNode(CategoryNode node, int depth) {
String indent = ” “.repeat(depth);
System.out.println(indent + node.getName() +
” (ID: ” + node.getId() +
“, 商品数: ” + node.getProductCount() + “)”);
for (CategoryNode child : node.getChildren()) {
printCategoryNode(child, depth + 1);
}
}
}
6.2 案例2：组织架构权限树
/**
* 组织架构权限树（支持权限继承）
*/
public class OrgPermissionTree {
static class PermissionNode {
private String id;
private String name;
private String parentId;
private Set
private List
public PermissionNode(String id, String name, String parentId) {
this.id = id;
this.name = name;
this.parentId = parentId;
this.permissions = new HashSet<>();
this.children = new ArrayList<>();
}
public void addPermission(String permission) {
this.permissions.add(permission);
}
public Set
Set
// 递归获取父节点的权限（权限继承）
PermissionNode current = this;
while (current.parentId != null) {
// 这里需要通过外部映射获取父节点，简化处理
break;
}
return allPerms;
}
// Getter方法…
public String getId() { return id; }
public String getName() { return name; }
public String getParentId() { return parentId; }
public Set
public List
public void addChild(PermissionNode child) { this.children.add(child); }
}
private Map
private List
/**
* 构建权限树并计算继承权限
*/
public void buildPermissionTree(List
this.nodeMap = new HashMap<>();
// 构建基础映射
for (PermissionNode node : nodes) {
nodeMap.put(node.getId(), node);
}
// 构建树结构
this.rootNodes = new ArrayList<>();
for (PermissionNode node : nodes) {
if (node.getParentId() == null || node.getParentId().isEmpty()) {
rootNodes.add(node);
} else {
PermissionNode parent = nodeMap.get(node.getParentId());
if (parent != null) {
parent.addChild(node);
}
}
}
// 计算继承权限（非递归方式，避免栈溢出）
calculateInheritedPermissionsNonRecursive();
}
/**
* 非递归计算继承权限（使用BFS）
*/
private void calculateInheritedPermissionsNonRecursive() {
Queue
Map
// 初始化根节点的继承权限为空
for (PermissionNode root : rootNodes) {
queue.offer(root);
inheritedPermissions.put(root.getId(), new HashSet<>());
}
while (!queue.isEmpty()) {
PermissionNode current = queue.poll();
Set
// 当前节点的所有权限（包括继承的）
Set
allPermissions.addAll(current.getPermissions());
// 存储当前节点的完整权限
inheritedPermissions.put(current.getId() + “_full”, allPermissions);
// 将子节点加入队列
for (PermissionNode child : current.getChildren()) {
// 子节点继承父节点的所有权限
inheritedPermissions.put(child.getId(), allPermissions);
queue.offer(child);
}
}
}
/**
* 检查用户是否有指定权限（递归检查）
*/
public boolean hasPermission(String nodeId, String permission) {
PermissionNode node = nodeMap.get(nodeId);
if (node == null) return false;
// 检查自身权限
if (node.getPermissions().contains(permission)) {
return true;
}
// 递归检查父节点权限
return checkParentPermission(node, permission);
}
private boolean checkParentPermission(PermissionNode node, String permission) {
if (node.getParentId() == null || node.getParentId().isEmpty()) {
return false;
}
PermissionNode parent = nodeMap.get(node.getParentId());
if (parent == null) return false;
if (parent.getPermissions().contains(permission)) {
return true;
}
return checkParentPermission(parent, permission);
}
/**
* 获取节点的所有有效权限（包括继承的）
*/
public Set
PermissionNode node = nodeMap.get(nodeId);
if (node == null) return new HashSet<>();
Set
collectPermissions(node, permissions);
return permissions;
}
private void collectPermissions(PermissionNode node, Set
permissions.addAll(node.getPermissions());
if (node.getParentId() != null && !node.getParentId().isEmpty()) {
PermissionNode parent = nodeMap.get(node.getParentId());
if (parent != null) {
collectPermissions(parent, permissions);
}
}
}
/**
* 打印权限树（显示权限信息）
*/
public void printPermissionTree() {
for (PermissionNode root : rootNodes) {
printPermissionNode(root, 0);
}
}
private void printPermissionNode(PermissionNode node, int depth) {
String indent = ” “.repeat(depth);
String perms = String.join(“, “, node.getPermissions());
System.out.println(indent + node.getName() +
” (ID: ” + node.getId() +
“, 权限: [” + perms + “])”);
for (PermissionNode child : node.getChildren()) {
printPermissionNode(child, depth + 1);
}
}
}
6.3 案例3：文件系统目录树
import java.io.File;
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.*;
import java.util.stream.Collectors;
/**
* 文件系统目录树构建器
*/
public class FileSystemTreeBuilder {
static class FileNode {
private String name;
private String absolutePath;
private boolean isDirectory;
private long size;
private long lastModified;
private List
public FileNode(String name, String absolutePath, boolean isDirectory,
long size, long lastModified) {
this.name = name;
this.absolutePath = absolutePath;
this.isDirectory = isDirectory;
this.size = size;
this.lastModified = lastModified;
this.children = new ArrayList<>();
}
// Getter方法…
public String getName() { return name; }
public String getAbsolutePath() { return absolutePath; }
public boolean isDirectory() { return isDirectory; }
public long getSize() { return size; }
public long getLastModified() { return lastModified; }
public List
public void addChild(FileNode child) { this.children.add(child); }
/**
* 获取文件大小的可读格式
*/
public String getFormattedSize() {
if (size < 1024) return size + " B";
if (size < 1024 * 1024) return String.format("%.2f KB", size / 1024.0);
if (size < 1024 * 1024 * 1024) return String.format("%.2f MB", size / (1024.0 * 1024.0));
return String.format("%.2f GB", size / (1024.0 * 1024.0 * 1024.0));
}
/**
* 获取最后修改时间的可读格式
*/
public String getFormattedLastModified() {
return new Date(lastModified).toString();
}
}
/**
* 递归构建文件系统树
*/
public static FileNode buildFileSystemTree(String rootPath) throws IOException {
File rootDir = new File(rootPath);
if (!rootDir.exists() || !rootDir.isDirectory()) {
throw new IllegalArgumentException("Invalid directory path: " + rootPath);
}
return buildFileNodeRecursive(rootDir);
}
private static FileNode buildFileNodeRecursive(File file) {
FileNode node = new FileNode(
file.getName(),
file.getAbsolutePath(),
file.isDirectory(),
file.length(),
file.lastModified()
);
if (file.isDirectory()) {
File[] children = file.listFiles();
if (children != null) {
for (File child : children) {
// 跳过隐藏文件和系统文件（可选）
if (child.getName().startsWith(".")) continue;
FileNode childNode = buildFileNodeRecursive(child);
node.addChild(childNode);
}
}
}
return node;
}
/**
* 非递归构建文件系统树（使用NIO.2）
*/
public static FileNode buildFileSystemTreeNonRecursive(String rootPath) throws IOException {
Path rootDir = Paths.get(rootPath);
if (!Files.isDirectory(rootDir)) {
throw new IllegalArgumentException("Invalid directory path: " + rootPath);
}
// 使用栈进行深度优先遍历
Stack
Map
stack.push(rootDir);
while (!stack.isEmpty()) {
Path current = stack.pop();
try {
BasicFileAttributes attrs = Files.readAttributes(current, BasicFileAttributes.class);
FileNode node = new FileNode(
current.getFileName().toString(),
current.toAbsolutePath().toString(),
attrs.isDirectory(),
attrs.size(),
attrs.lastModifiedTime().toMillis()
);
nodeMap.put(current, node);
if (attrs.isDirectory()) {
try (DirectoryStream
List
stream.forEach(children::add);
// 反向压栈以保持正确的遍历顺序
for (int i = children.size() – 1; i >= 0; i–) {
Path child = children.get(i);
if (!child.getFileName().toString().startsWith(“.”)) {
stack.push(child);
}
}
}
}
} catch (IOException e) {
// 跳过无法访问的文件
System.err.println(“Cannot access: ” + current);
}
}
// 构建父子关系
for (Map.Entry
Path path = entry.getKey();
FileNode node = entry.getValue();
Path parentPath = path.getParent();
if (parentPath != null && nodeMap.containsKey(parentPath)) {
nodeMap.get(parentPath).addChild(node);
}
}
return nodeMap.get(rootDir);
}
/**
* 打印文件树（带缩进和统计信息）
*/
public static void printFileSystemTree(FileNode node, int depth) {
if (node == null) return;
String indent = ” “.repeat(depth);
String type = node.isDirectory() ? “[DIR] ” : “[FILE] “;
String size = node.isDirectory() ? “” : ” (” + node.getFormattedSize() + “)”;
System.out.println(indent + type + node.getName() + size);
// 按名称排序
List
.sorted(Comparator.comparing(FileNode::isDirectory)
.thenComparing(FileNode::getName))
.collect(Collectors.toList());
for (FileNode child : sortedChildren) {
printFileSystemTree(child, depth + 1);
}
}
/**
* 统计文件树信息
*/
public static TreeStats calculateTreeStats(FileNode root) {
TreeStats stats = new TreeStats();
calculateStatsRecursive(root, stats);
return stats;
}
private static void calculateStatsRecursive(FileNode node, TreeStats stats) {
if (node.isDirectory()) {
stats.totalDirectories++;
} else {
stats.totalFiles++;
stats.totalSize += node.getSize();
}
for (FileNode child : node.getChildren()) {
calculateStatsRecursive(child, stats);
}
}
static class TreeStats {
int totalFiles = 0;
int totalDirectories = 0;
long totalSize = 0;
@Override
public String toString() {
return String.format(“文件: %d, 目录: %d, 总大小: %s”,
totalFiles, totalDirectories, formatSize(totalSize));
}
private String formatSize(long size) {
if (size < 1024) return size + " B";
if (size < 1024 * 1024) return String.format("%.2f KB", size / 1024.0);
if (size < 1024 * 1024 * 1024) return String.format("%.2f MB", size / (1024.0 * 1024.0));
return String.format("%.2f GB", size / (1024.0 * 1024.0 * 1024.0));
}
}
}
7. 性能对比与选择建议
7.1 递归 vs 非递归性能对比
场景
递归实现
非递归实现
推荐方案
小规模数据（<1000节点）
代码简洁，性能良好
代码复杂，性能相近
递归实现
中等规模数据（1000-10000节点）
可能出现栈溢出
性能稳定
非递归实现
大规模数据（>10000节点）
容易栈溢出
性能优秀
非递归实现
需要并行处理
难以并行化
易于并行化
非递归实现
需要复杂遍历控制
灵活性有限
控制精细
非递归实现
7.2 选择建议
优先考虑递归的情况：
数据量较小（<1000节点）
代码可读性要求高
快速原型开发
树结构相对简单
优先考虑非递归的情况：
数据量较大或不确定
性能要求严格
需要并行处理
需要精细控制遍历过程
生产环境的稳定代码
混合方案：
使用递归构建基础结构
使用非递归进行遍历和查询
根据不同场景选择合适的方法
8. 常见问题与解决方案
8.1 栈溢出问题
问题：
递归深度过大导致栈溢出
解决方案：
// 1. 增加JVM栈大小（不推荐）
// java -Xss2m YourApp
// 2. 改用非递归实现（推荐）
// 使用栈或队列模拟递归
// 3. 尾递归优化（Java不支持，但可以手动优化）
// 将递归转换为迭代
8.2 内存占用过高
问题：
树结构占用过多内存
解决方案：
// 1. 使用基本数据类型
// 避免包装类，使用int代替Integer
// 2. 延迟加载
// 只在需要时加载子节点
// 3. 使用压缩存储
// 对于稀疏树，使用特殊数据结构
// 4. 对象池
// 复用节点对象，减少GC压力
8.3 性能瓶颈
问题：
构建或查询速度慢
解决方案：
// 1. 使用缓存
Map
// 2. 索引优化
Map
// 3. 批量操作
// 一次性处理多个节点，减少循环次数
// 4. 并行处理
// 使用并行流或线程池
9. 最佳实践总结
9.1 设计原则
单一职责：
每个类只负责一个功能
开闭原则：
对扩展开放，对修改关闭
依赖倒置：
依赖抽象而非具体实现
接口隔离：
定义细粒度的接口
9.2 编码规范
命名清晰：
类名、方法名要有明确含义
注释完整：
公共API必须有JavaDoc
异常处理：
合理处理异常，不吞掉异常
资源管理：
使用try-with-resources管理资源
9.3 性能优化
预分配容量：
避免频繁扩容
使用缓存：
减少重复计算
并行处理：
充分利用多核CPU
延迟加载：
按需加载数据
9.4 测试建议
单元测试：
覆盖核心算法
边界测试：
空数据、单节点、深层树
性能测试：
大规模数据下的表现
并发测试：
多线程环境下的稳定性
10. 扩展阅读
10.1 相关数据结构
二叉树：
左右子节点的特殊树
B树/B+树：
数据库索引常用
红黑树：
Java TreeMap的实现基础
Trie树：
字符串前缀匹配
10.2 Java集合中的树
TreeMap：
基于红黑树的有序Map
TreeSet：
基于红黑树的有序Set
PriorityQueue：
基于堆的优先队列
10.3 性能监控工具
JProfiler：
Java性能分析工具
VisualVM：
JDK自带的监控工具
Arthas：
阿里开源的诊断工具
结语
树结构是Java开发中不可或缺的重要概念。通过本文的学习，读者应该掌握了从基础定义到高级实现的完整知识体系。在实际开发中，选择合适的实现方式需要根据具体场景、数据规模和性能要求来决定。
记住，没有最好的实现，只有最合适的实现。在实际项目中，建议先用递归实现快速验证思路，然后根据性能测试结果决定是否需要优化为非递归实现。同时，保持代码的可读性和可维护性同样重要。
希望本文能够帮助你在Java树结构开发中游刃有余，构建出高效、稳定的树结构应用！