Какие существуют алгоритмы обхода деревьев? Опишите их и приведите примеры на Go.

Существует два основных подхода к обходу деревьев: в глубину (DFS) и в ширину (BFS).

1. Обход в глубину (DFS — Depth-First Search)

Алгоритм следует по одному пути до самого конца, прежде чем вернуться и исследовать другие ветви. Для реализации обычно используется рекурсия (неявный стек) или итеративный подход с явным стеком.

Виды DFS:

• Прямой обход (Pre-order): Корень -> Левое поддерево -> Правое поддерево. Применение: создание копии дерева, получение префиксной записи выражения.
• Центрированный (симметричный) обход (In-order): Левое поддерево -> Корень -> Правое поддерево. Применение: в бинарном дереве поиска (BST) этот обход возвращает элементы в отсортированном порядке.
• Обратный обход (Post-order): Левое поддерево -> Правое поддерево -> Корень. Применение: удаление узлов дерева (сначала удаляются потомки, затем родитель), получение постфиксной записи выражения.

Пример (Pre-order на Go):

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func preOrderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Println(root.Val) // Посещаем корень
    preOrderTraversal(root.Left)  // Идем в левое поддерево
    preOrderTraversal(root.Right) // Идем в правое поддерево
}

2. Обход в ширину (BFS — Breadth-First Search)

Алгоритм исследует дерево уровень за уровнем, слева направо. Для реализации используется очередь (Queue).

Применение: поиск кратчайшего пути в невзвешенном графе/дереве, нахождение всех узлов на определенной глубине.

Пример (BFS на Go):

func bfsTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    // Создаем очередь и добавляем в нее корень дерева
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        // Извлекаем узел из начала очереди
        node := queue[0]
        queue = queue[1:]

        fmt.Println(node.Val) // Обрабатываем узел

        // Добавляем дочерние узлы в конец очереди
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
}