本文目录导读：
- 目录导读
- 为什么树形数据遍历是Java开发者的必修课？
- 树形数据结构的基本定义与Java实现
- 深度优先遍历（DFS）实战案例：递归与迭代
- 广度优先遍历（BFS）实战案例：队列的应用
- 常见面试问答与避坑指南
- 总结：如何选择最适合的遍历方式？
Java案例详解：如何高效遍历树形数据？从递归到栈，一文掌握核心技巧
目录导读
- 为什么树形数据遍历是Java开发者的必修课？
- 树形数据结构的基本定义与Java实现
- 深度优先遍历（DFS）实战案例：递归与迭代
- 广度优先遍历（BFS）实战案例：队列的应用
- 常见面试问答与避坑指南
- 如何选择最适合的遍历方式？
为什么树形数据遍历是Java开发者的必修课？
在企业级Java应用中，树形数据无处不在：组织架构、分类目录、评论回复、菜单权限、甚至文件系统，如果你写过后台管理系统，大概率遇到过“无限级分类”的递归查询性能问题。遍历树形数据是解析、转换、渲染这类结构的核心技能。
更关键的是，面试中90%的树问题考查的不是“会不会写递归”，而是“能否在递归与迭代间灵活切换，并分析时空复杂度”。
问：遍历树形数据最常见的误区是什么？ 答：很多人只掌握递归，忽略了当树深度过大时（比如超过1000层）递归会导致栈溢出（StackOverflowError）。真正的生产级代码必须掌握非递归（迭代）写法。
树形数据结构的基本定义与Java实现
我们先定义一个通用的树节点类 TreeNode：
public class TreeNode {
private Long id;
private Long parentId;
private String name;
private List<TreeNode> children;
// 构造函数、getter/setter省略
}
在实际业务中，数据库通常存储的是 id, parentId, name 这种扁平列表，第一步需要将List转为Tree：
public List<TreeNode> buildTree(List<TreeNode> flatList) {
Map<Long, TreeNode> map = new HashMap<>();
List<TreeNode> roots = new ArrayList<>();
for (TreeNode node : flatList) {
map.put(node.getId(), node);
}
for (TreeNode node : flatList) {
if (node.getParentId() == null) {
roots.add(node);
} else {
TreeNode parent = map.get(node.getParentId());
if (parent != null) {
parent.getChildren().add(node);
}
}
}
return roots;
}
问：为什么用Map而不是双重循环？ 答：时间复杂度从O(n²)降为O(n),大数据量下这是基本素养。
深度优先遍历（DFS）实战案例：递归与迭代
1 递归版DFS（最直观）
遍历每个节点并输出其完整路径：
public void dfsRecursive(TreeNode node, String prefix) {
System.out.println(prefix + node.getName());
if (node.getChildren() != null) {
for (TreeNode child : node.getChildren()) {
dfsRecursive(child, prefix + " ");
}
}
}
优点：代码简洁，易于理解。
缺点：每次递归调用都创建新的栈帧,树深度过大时可能栈溢出。
2 迭代版DFS（使用栈）
手动模拟系统的调用栈：
public void dfsIterative(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.getName());
// 先压入右子节点，保证左子节点先出栈（前序遍历）
if (node.getChildren() != null) {
List<TreeNode> children = node.getChildren();
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}
}
}
优点：无栈溢出风险，可精确控制遍历顺序。
缺点：代码稍复杂,需要手动管理栈。
问：迭代版DFS如何实现后序遍历？ 答：需要额外标记每个节点的访问状态（visited flag）,或使用两个栈。
广度优先遍历（BFS）实战案例：队列的应用
BFS常用于“按层输出”或“查找最短路径”。
public void bfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
System.out.print(node.getName() + " ");
if (node.getChildren() != null) {
for (TreeNode child : node.getChildren()) {
queue.offer(child);
}
}
}
System.out.println(); // 换行表示新层
}
}
输出示例：
根节点
子节点A 子节点B
子节点A1 子节点A2 子节点B1问：什么时候必须用BFS而不是DFS？ 答：当需要最短路径或层级相关的业务逻辑时，如：找到组织架构中两个员工之间的层级距离。
常见面试问答与避坑指南
Q1：递归遍历树，性能如何？
答：如果树深度不超过1000，递归性能足够；但如果是超大型树（如文件系统），建议迭代，递归的优点是“代码即逻辑”，易于维护；迭代的优点是“可控栈深度”。
Q2：如何遍历时过滤节点？
答：在遍历循环中加入判断条件：
public void filterAndTraverse(TreeNode node, Predicate<TreeNode> filter) {
if (filter.test(node)) {
System.out.println(node.getName());
}
if (node.getChildren() != null) {
for (TreeNode child : node.getChildren()) {
filterAndTraverse(child, filter);
}
}
}
Q3：如何遍历并收集所有节点的某些属性？
答：使用 Stream + flatMap 或递归收集：
public List<String> collectNames(TreeNode root) {
List<String> names = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
names.add(node.getName());
if (node.getChildren() != null) {
node.getChildren().forEach(stack::push);
}
}
return names;
}
Q4：树形数据在数据库中如何高效获取？
答：尽量避免递归SQL（如MySQL的 WITH RECURSIVE 在某些版本性能差）,推荐方案：
- 使用 Nested Set（左右值模型）预排序
- 或使用 Closure Table（闭包表）存储所有祖先-后代关系
- 或直接一次性加载所有节点，在内存中构建树（适用于节点数 < 10万）
如何选择最适合的遍历方式？
| 场景 | 推荐方式 | 原因 |
|---|---|---|
| 树深度小（<500） | 递归DFS | 代码最简洁 |
| 树深度大（>1000） | 迭代DFS（栈） | 防止栈溢出 |
| 需要按层展示 | 迭代BFS（队列） | 天然层级结构 |
| 需要收集所有节点数据 | 迭代DFS + 集合 | 可控性强 |
| 面试手写 | 先写递归，再提迭代优化 | 展现技术深度 |
最后一条建议：永远不要假设你的树“很浅”，在生产代码中，优先使用迭代方式遍历,或者为递归设置最大深度保护。
提示：以上代码可直接在您的IDE中运行，如需完整源码包，请搜索“Java树形遍历工具类 TreeUtil”获取社区开源版本（如 HuTool 的 TreeNodeUtil）。
保持学习，每周精进，如果你也有树形数据遍历的独特技巧，欢迎在评论区分享。
