Какие методы обхода дерева ты можешь назвать и как они работают?

Основные методы обхода дерева — это:

1. Обход в глубину (DFS):

   • Pre-order (прямой обход): сначала посещается корень, затем рекурсивно левое поддерево, потом правое.
   • In-order (симметричный обход): сначала левое поддерево, затем корень, потом правое поддерево. Часто используется для бинарных деревьев поиска, чтобы получить отсортированный порядок.
   • Post-order (обратный обход): сначала левое поддерево, потом правое, затем корень.

2. Обход в ширину (BFS):

   • Посещение узлов по уровням, начиная с корня, затем все узлы первого уровня, потом второго и так далее. Обычно реализуется с помощью очереди.

Пример обхода в глубину (pre-order) на Java:

void preOrder(Node node) {
    if (node == null) return;
    System.out.println(node.value);
    preOrder(node.left);
    preOrder(node.right);
}