Проверяет знание методов traversal для деревьев (бинарных, N-арных).
DFS (Depth-First Search):
In-order (левый → корень → правый).
Pre-order (корень → левый → правый).
Post-order (левый → правый → корень).
BFS (Breadth-First Search):
По уровням (очередь).
Pre-order:
void dfsPreOrder(Node node) {
if (node == null) return;
System.out.print(node.value + " "); // Корень
dfsPreOrder(node.left); // Левый
dfsPreOrder(node.right); // Правый
}In-order (для бинарного дерева поиска выводит значения в порядке возрастания):
void dfsInOrder(Node node) {
if (node == null) return;
dfsInOrder(node.left); // Левый
System.out.print(node.value + " "); // Корень
dfsInOrder(node.right); // Правый
}void bfs(Node root) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.value + " ");
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}Пример дерева:
1
/ \
2 3
/ \
4 5Pre-order: 1 → 2 → 4 → 5 → 3.
In-order: 4 → 2 → 5 → 1 → 3.
BFS: 1 → 2 → 3 → 4 → 5.
Вывод:
DFS — для поиска элементов, проверки структуры.
BFS — для поиска кратчайшего пути (например, в графах).