Объясните механизм поиска элемента в бинарном дереве и каким образом осуществляется его обход

В бинарном дереве поиска (BST) поиск элемента происходит следующим образом:

1. Начинаем с корня дерева.
2. Сравниваем искомое значение с текущим узлом:
   • Если значение равно, элемент найден.
   • Если значение меньше, переходим в левое поддерево.
   • Если значение больше, переходим в правое поддерево.
3. Повторяем процесс, пока не найдем элемент или не достигнем пустого узла (элемент отсутствует).

Обход бинарного дерева — это способ последовательного посещения всех узлов. Основные виды обхода:

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

Пример поиска и обхода на Go:

package main
import "fmt"

type Node struct {
    Value int
    Left, Right *Node
}

func (n *Node) Search(val int) *Node {
    if n == nil || n.Value == val {
        return n
    }
    if val < n.Value {
        return n.Left.Search(val)
    }
    return n.Right.Search(val)
}

func (n *Node) InOrder() {
    if n == nil {
        return
    }
    n.Left.InOrder()
    fmt.Print(n.Value, " ")
    n.Right.InOrder()
}

func main() {
    root := &Node{Value: 10}
    root.Left = &Node{Value: 5}
    root.Right = &Node{Value: 15}

    node := root.Search(5)
    if node != nil {
        fmt.Println("Найден узел со значением:", node.Value)
    } else {
        fmt.Println("Элемент не найден")
    }

    fmt.Print("Обход in-order: ")
    root.InOrder() // Выведет: 5 10 15
}