Class TreeTraversalUtil

java.lang.Object

cloud.opencode.base.collections.tree.TreeTraversalUtil

public final class TreeTraversalUtil
extends Object

TreeTraversalUtil - Tree Traversal Utilities TreeTraversalUtil - 树遍历工具

Provides utilities for traversing tree structures.

提供遍历树结构的工具。

Features | 主要功能:

• Pre-order traversal - 前序遍历
• Post-order traversal - 后序遍历
• Level-order (BFS) traversal - 层序（广度优先）遍历
• Generic tree support - 通用树支持

Usage Examples | 使用示例:

// Define a tree node with children getter - 定义获取子节点的树节点
TreeTraversalUtil.preOrder(rootNode, Node::getChildren, node -> {
    System.out.println(node.getValue());
});

// Level-order traversal - 层序遍历
TreeTraversalUtil.levelOrder(rootNode, Node::getChildren, node -> {
    System.out.println(node.getValue());
});

// Collect all nodes - 收集所有节点
List<Node> allNodes = TreeTraversalUtil.collectPreOrder(rootNode, Node::getChildren);

Security | 安全性:

• Thread-safe: Yes (stateless utility) - 是（无状态工具）
• Null-safe: No (root must not be null) - 否（根节点不能为null）

Performance | 性能特性:

• Time complexity: O(n) for all traversals where n is the number of nodes - 时间复杂度: 所有遍历均为 O(n)，n为节点数量
• Space complexity: O(h) for pre/post-order where h is the tree height; O(n) for level-order queue - 空间复杂度: 前/后序遍历为 O(h)，h为树高；层序遍历队列为 O(n)

Since:

JDK 25, opencode-base-collections V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

• OpenCode.cloud

Method Summary

Modifier and Type	Method	Description
static <T> List<List<T>>	collectByLevel(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Collect nodes by level.
static <T> List<T>	collectLevelOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Collect all nodes in level-order.
static <T> List<T>	collectPostOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Collect all nodes in post-order.
static <T> List<T>	collectPreOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Collect all nodes in pre-order.
static <T> int	count(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Count the total number of nodes.
static <T> int	depth(T root, Function<T, ? extends Iterable<T>> childrenGetter)	Calculate the depth (height) of the tree.
static <T> T	find(T root, Function<T, ? extends Iterable<T>> childrenGetter, Predicate<T> predicate)	Find a node by predicate.
static <T> List<T>	findAll(T root, Function<T, ? extends Iterable<T>> childrenGetter, Predicate<T> predicate)	Find all nodes matching predicate.
static <T> void	levelOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter, Consumer<T> action)	Perform level-order (BFS) traversal.
static <T> List<T>	pathTo(T root, T target, Function<T, ? extends Iterable<T>> childrenGetter)	Get the path from root to a node.
static <T> void	postOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter, Consumer<T> action)	Perform post-order traversal.
static <T> void	preOrder(T root, Function<T, ? extends Iterable<T>> childrenGetter, Consumer<T> action)	Perform pre-order traversal.
static <T> void	preOrderIterative(T root, Function<T, ? extends Iterable<T>> childrenGetter, Consumer<T> action)	Perform pre-order traversal iteratively (non-recursive).

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

preOrder

public static <T> void preOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Consumer<T> action)

Perform pre-order traversal. 执行前序遍历。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

action - action to perform on each node | 对每个节点执行的操作

preOrderIterative

public static <T> void preOrderIterative(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Consumer<T> action)

Perform pre-order traversal iteratively (non-recursive). 执行迭代式（非递归）前序遍历。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

action - action to perform on each node | 对每个节点执行的操作

collectPreOrder

public static <T> List<T> collectPreOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Collect all nodes in pre-order. 按前序收集所有节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

list of nodes in pre-order | 前序节点列表

postOrder

public static <T> void postOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Consumer<T> action)

Perform post-order traversal. 执行后序遍历。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

action - action to perform on each node | 对每个节点执行的操作

collectPostOrder

public static <T> List<T> collectPostOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Collect all nodes in post-order. 按后序收集所有节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

list of nodes in post-order | 后序节点列表

levelOrder

public static <T> void levelOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Consumer<T> action)

Perform level-order (BFS) traversal. 执行层序（广度优先）遍历。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

action - action to perform on each node | 对每个节点执行的操作

collectLevelOrder

public static <T> List<T> collectLevelOrder(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Collect all nodes in level-order. 按层序收集所有节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

list of nodes in level-order | 层序节点列表

collectByLevel

public static <T> List<List<T>> collectByLevel(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Collect nodes by level. 按层收集节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

list of levels, each containing nodes at that level | 层列表，每层包含该层的节点

depth

public static <T> int depth(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Calculate the depth (height) of the tree. 计算树的深度（高度）。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

the depth of the tree | 树的深度

count

public static <T> int count(T root,
 Function<T, ? extends Iterable<T>> childrenGetter)

Count the total number of nodes. 计算节点总数。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

the total number of nodes | 节点总数

find

public static <T> T find(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Predicate<T> predicate)

Find a node by predicate. 根据谓词查找节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

predicate - the predicate | 谓词

Returns:

the found node or null | 找到的节点或 null

findAll

public static <T> List<T> findAll(T root,
 Function<T, ? extends Iterable<T>> childrenGetter,
 Predicate<T> predicate)

Find all nodes matching predicate. 查找所有匹配谓词的节点。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

childrenGetter - function to get children | 获取子节点的函数

predicate - the predicate | 谓词

Returns:

list of matching nodes | 匹配节点列表

pathTo

public static <T> List<T> pathTo(T root,
 T target,
 Function<T, ? extends Iterable<T>> childrenGetter)

Get the path from root to a node. 获取从根到节点的路径。

Type Parameters:

T - node type | 节点类型

Parameters:

root - the root node | 根节点

target - the target node | 目标节点

childrenGetter - function to get children | 获取子节点的函数

Returns:

the path from root to target, or empty list if not found | 从根到目标的路径，如果未找到则为空列表