Ответ
Существует два основных подхода к обходу деревьев: в глубину (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)
}
}
}Ответ 18+ 🔞
Так, слушай, вот сидишь ты, бывает, перед деревом, а оно, сука, такое большое, что глаза разбегаются. И тут встаёт вопрос: как его, блядь, обойти, чтобы ни одну ветку не пропустить? А вариантов-то, оказывается, дохуя!
Вот есть два главных подхода, как по жизни: либо вглубь, либо вширь. Прям как в психологии, ёпта.
Первый — обход в глубину (DFS). Это когда ты такой упёртый, как Герасим из "Муму", и идешь по одной дорожке до самого конца, пока в тупик не упрёшься, а потом возвращаешься и начинаешь другую. Внутри него ещё три разновидности, как три богатыря, блядь:
- Прямой (Pre-order): Сначала корень — бах! — потом налево, потом направо. Как будто сначала себя похвалил, а потом уже по сторонам смотришь. Нужно, например, дерево скопировать или выражение в префиксной записи получить.
- Симметричный (In-order): Сначала налево, потом корень, потом направо. В бинарном дереве поиска так отсортированный список получишь — красота, блядь!
- Обратный (Post-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) // Идем в правое поддерево
}Второй подход — обход в ширину (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)
}
}
}Вот и вся магия, блядь. Выбирай, что тебе больше по душе: копать до упора в одну точку или методично всё прочёсывать. Главное — не заблудиться, а то так и останешься в этом дереве навсегда, в рот меня чих-пых!