- 使用 Guava 遍历树形结构
Guava 的 Traverser 类是一个非常有用的工具，它可以处理树形结构、图的遍历。通过使用这个类，你可以轻松实现各种树的深度优先搜索（DFS）、广度优先搜索（BFS）操作。
1.1 Traverser 类的使用
实际上，需要遍历树时，只需要指定 父节点 => 子节点集合 的映射方法即可。
record Node(String name, @NonNull List<Node> children) {}
class TreeTraversalDemo {
public static void main(String[] args) {
// 构建树
Node leaf1 = new Node("Leaf1", List.of());
Node leaf2 = new Node("Leaf2", List.of());
Node child1 = new Node("Child1", List.of(leaf1));
Node child2 = new Node("Child2", List.of(leaf2));
Node root = new Node("Root", List.of(child1, child2));
// Traverser: Guava 提供的不可变对象，封装了遍历算法
Traverser<Node> traverser = Traverser.forTree(Node::children);
// breadthFirst 方法返回 Iterator 类型
List<String> bfs = Streams.stream(traverser.breadthFirst(root))
.map(Node::name)
.toList();
System.out.println("bfs = " + bfs);
List<String> dfsPostOrder = Streams.stream(traverser.depthFirstPostOrder(root))
.map(Node::name)
.toList();
System.out.println("dfsPostOrder = " + dfsPostOrder);
List<String> dfsPreOrder = Streams.stream(traverser.depthFirstPreOrder(root))
.map(Node::name)
.toList();
System.out.println("dfsPreOrder = " + dfsPreOrder);
}
}
输入的树为：
Root
/
Child1 Child2
| |
Leaf1 Leaf2
输出结果为：
bfs = [Root, Child1, Child2, Leaf1, Leaf2]
dfsPostOrder = [Leaf1, Child1, Leaf2, Child2, Root]
dfsPreOrder = [Root, Child1, Leaf1, Child2, Leaf2]
1.2 遍历结果是懒计算的
注意：遍历的结果是懒计算的，Traverser#breadthFirst 等返回返回 Iterator 类型。
不要在遍历中改变节点间的关系。如果想要改变，选择需要改变的节点，显式指定计算后（如 iterator -> stream -> list, 将遍历结果保存起来)再修改结果。
iterator 可以多次求值，其逻辑相比 stream 只能求解一次来说更违反人的认知逻辑，因为多次求解的结果可能不同。这也是为什么 Stream 只能使用一次的原因之一。
建议优先不使用懒计算。只有在需要使用懒计算时，再使用懒计算。
1.3 使用流式编程进行后续操作
流式编程可能是函数式编程中流传最广的编程模式，你可以对遍历结果（Iterator)进行各种操作，如 find、filter、peek、map、flatMap、reduce、collect等操作。
有两种编程模式可以选择，Guava 提供了 Iterables 工具类，可以实现流式编程；更推荐转换为 Stream 流，其为官方推荐的编程模式，也便于他人阅读代码和交流，Guava 中可以使用 Streams#stream 方法将 iterator 转换为流。
示例：查找树中的特定节点
// 普通实现
Node targetNode = null;
for (Node node : traverser.preOrderTraversal(rootNode)) {
if (node.name.equals("目标节点")) {
targetNode = node;
break;
}
}
// 流式实现：更简单易懂
Optional<Node> targetNode = Streams.stream(traverser.depthFirstPreOrder(rootNode))
.findFirst(node -> "目标节点".equals(node.name));
1.4 树形结构不一定是显式的
实际上，我们不必在每一个节点都维护其子节点，比如Node#getChildren方法。有时候，可以通过外部的 Map, Multimap 实现相同的功能，这样做的好处是无需修改原有的类设计，图（树）和类设计之间解耦，减轻编码负担。
-
使用 Graph 创建树
Guava 中创建树可以使用 builder 模式进行创建，我们无需关注其底层实现，不管其底层是邻接表还是哈希表，Guava 会尽可能保证底层实现更高效。
Guava支持可变推荐优先使用不可变对象，其有多种好处，如方便理解、便于测试、支持并发、底层实现可以更高效等。
以下是使用 GraphBuilder 创建树形结构的示例：
class OrganizationStructureDemo {record OrganizationNode(String name) {}
public static void main(String[] args) {
// 创建组织节点
// 这里纠结使用 cEO 还是 ceo？有没有人给出自己的理解？
OrganizationNode cEO = new OrganizationNode("CEO");
OrganizationNode cTO = new OrganizationNode("CTO");
OrganizationNode cFO = new OrganizationNode("CFO");
OrganizationNode devLead = new OrganizationNode("Dev Lead");
OrganizationNode dev1 = new OrganizationNode("Developer 1");
OrganizationNode dev2 = new OrganizationNode("Developer 2");
OrganizationNode financeLead = new OrganizationNode("Finance Lead");
OrganizationNode accountant1 = new OrganizationNode("Accountant 1");
OrganizationNode accountant2 = new OrganizationNode("Accountant 2");// 使用 GraphBuilder 构建组织架构的下属关系（从上级指向下级） ImmutableGraph<OrganizationNode> organizationGraph = GraphBuilder.directed() // 树是有方向的（从上级指向下级） .<OrganizationNode>immutable() .putEdge(cEO, cTO) // CEO -> CTO .putEdge(cEO, cFO) // CEO -> CFO .putEdge(cTO, devLead) // CTO -> Dev Lead .putEdge(devLead, dev1) // Dev Lead -> Developer 1 .putEdge(devLead, dev2) // Dev Lead -> Developer 2 .putEdge(cFO, financeLead) // CFO -> Finance Lead .putEdge(financeLead, accountant1) // Finance Lead -> Accountant 1 .putEdge(financeLead, accountant2) // Finance Lead -> Accountant 2 .build(); // 遍历和显示节点关系 System.out.println("Organization Structure (Subordinate Relationships):"); organizationGraph.nodes() .forEach(node -> { System.out.println(node + " has subordinates: "); organizationGraph.successors(node) .forEach(successor -> System.out.println(" -> " + successor)); });}
}
结果如下：
Organization Structure (Subordinate Relationships):
OrganizationNode[name=CEO] has subordinates:
-> OrganizationNode[name=CTO]
-> OrganizationNode[name=CFO]
OrganizationNode[name=CTO] has subordinates:
-> OrganizationNode[name=Dev Lead]
OrganizationNode[name=CFO] has subordinates:
-> OrganizationNode[name=Finance Lead]
OrganizationNode[name=Dev Lead] has subordinates:
-> OrganizationNode[name=Developer 1]
-> OrganizationNode[name=Developer 2]
OrganizationNode[name=Developer 1] has subordinates:
OrganizationNode[name=Developer 2] has subordinates:
OrganizationNode[name=Finance Lead] has subordinates:
-> OrganizationNode[name=Accountant 1]
-> OrganizationNode[name=Accountant 2]
OrganizationNode[name=Accountant 1] has subordinates:
OrganizationNode[name=Accountant 2] has subordinates:
- 锐评大多数 Tree 工具类
笔者认为：很多工具类的设计看似简化了对树的处理，添加了所谓的便利方法，实际上是在重复造轮子，同时徒增学习成本。不如熟读 Guava 文档，理解 Graph 的使用并结合流式编程、不可变对象实现相应需求。
以下我们来看看一些工具类的实现：
3.1 创建树
public class TreeUtil {
public static <E> List<E> makeTree(List<E> list, Predicate<E> rootCheck, BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> setSubChildren) {
return list.stream().filter(rootCheck).peek(x -> setSubChildren.accept(x, makeChildren(x, list, parentCheck, setSubChildren))).collect(Collectors.toList());
}
}
创建树的方法，奇怪的函数接口用法，不明所以，还不如用户手动维护。
Guava 中使用 builder 模式创建树或图，支持多种模式，比如有向图、无向图、权重图等等，请看第 2 节的示例。
3.2 过滤 filter
public static <E> List<E> filter(List<E> tree, Predicate<E> predicate, Function<E, List<E>> getChildren) {
return tree.stream().filter(item -> {
if (predicate.test(item)) {
List<E> children = getChildren.apply(item);
if (children != null && !children.isEmpty()) {
filter(children, predicate, getChildren);
}
return true;
}
return false;
}).collect(Collectors.toList());
}
//只保留id<5的节点
List<MenuVo> filterMenus =TreeUtil.filter(tree1,x->x.getId()<5,MenuVo::getSubMenus);
执行 Traverser -> Stream -> filter -> list 即可。
Traverser traverser = Traverser.forTree(MenuVo::getSubMenus);
List<MenuVo> menus = Streams.stream(traverser.breadthFirst(root))
.filter(x -> x.getId() < 5)
.toList();
3.3 打平 flat
public static <E> List<E> flat(List<E> tree, Function<E, List<E>> getSubChildren, Consumer<E> setSubChildren) {
List<E> res = new ArrayList<>();
forPostOrder(tree, item -> {
setSubChildren.accept(item);
res.add(item);
}, getSubChildren);
return res;
}
// 使用
List<Menu> flat = TreeUtil.flat(tree, Menu::getSubMenus,x->x.setSubMenus(null));
Assert.assertEquals(flat.size(),menuList.size());
flat.forEach(x->{
Assert.assertTrue(x.getSubMenus()==null);
});
设计工具类的原则：尽量避开副作用。Consumer 大多数情况都是具有副作用的。理想的设计应该是打平后，再使用consumer 进行消费。
打平即遍历，收集每一个节点到 List 中，可以使用 Stream 轻松实现。所以这个方法可以删除掉。
Java 已经提供了 Stream 流式编程的支持，所有的流式编程相关操作及其组合而成的工具方法都不必要了。
3.4 排序 sort
public static <E> List<E> sort(List<E> tree, Comparator<? super E> comparator, Function<E, List<E>> getChildren) {
for (E item : tree) {
List<E> childList = getChildren.apply(item);
if (childList != null && !childList.isEmpty()) {
sort(childList,comparator,getChildren);
}
}
// 依然是副作用的设计，需要 List 是可变的
tree.sort(comparator);
return tree;
}
实际上，图创建的时候就应该指定好同级节点顺序，Graph 默认是插入顺序，还支持自然排序，根据比较器排序等等，请看 ElementOrder。
ImmutableGraph<OrganizationNode> organizationGraph =
GraphBuilder.directed()
// 创建时指定排序即可
.nodeOrder(ElementOrder.sorted(Comparator.comparing(OrganizationNode::order)))
.immutable()
.putEdge(CEO, CTO) // CEO -> CTO
.putEdge(CEO, CFO) // CEO -> CFO
.putEdge(CTO, DevLead) // CTO -> Dev Lead
.putEdge(DevLead, Dev1) // Dev Lead -> Developer 1
.putEdge(DevLead, Dev2) // Dev Lead -> Developer 2
.putEdge(CFO, FinanceLead) // CFO -> Finance Lead
.putEdge(FinanceLead, Accountant1) // Finance Lead -> Accountant 1
.putEdge(FinanceLead, Accountant2) // Finance Lead -> Accountant 2
.build();
- 总结
对树形结构遍历是开发中常见的需求，使用 Guava 类库可以轻松实现树的创建和遍历。
以下是使用 Graph、Traverser 时的一些原则：
使用 builder 模式创建复杂对象
尽量使用不可变对象
不必自己在节点中维护关联关系
仅在需要进行懒计算的时候使用
优先使用流式编程
工具类库的设计原则：
应该尽量避免副作用，尽量支持不可变数据结构
避免重复造轮子
多使用不可变类型，如 Traverser，ElementOrder
