Бинарное дерево и обходы

Что такое дерево

Дерево — иерархическая структура из узлов. У дерева есть корень (верхний узел), у каждого узла — потомки. Бинарное дерево — то, где у узла не больше двух детей: left и right. Узлы без детей называют листьями. Деревья моделируют файловую систему, HTML-страницу (DOM), дерево решений.

Три обхода в глубину (DFS)

Обойти дерево — значит посетить все узлы. Обходы в глубину рекурсивны и различаются моментом, когда мы «посещаем» сам узел относительно его поддеревьев:

• pre-order (прямой): узел → левое → правое.
• in-order (симметричный): левое → узел → правое.
• post-order (обратный): левое → правое → узел.

Обход в ширину (BFS) по уровням

BFS посещает узлы уровень за уровнем: сначала корень, потом всех его детей, потом внуков. Реализуется очередью: достаём узел, печатаем, кладём в очередь его детей. Этот приём вы уже видели — очередь deque из модуля про структуры данных.

Вернётся 3: путь 1 → 2 → 4 (или 1 → 2 → 5) содержит три узла. Высота считается рекурсивно: высота узла = 1 + максимум из высот поддеревьев, а пустое поддерево даёт 0.

⚠️ Частые ошибки новичков

Ошибка. Забыть проверку if node is None в рекурсивном обходе. Тогда при попытке обратиться к node.left у несуществующего узла будет AttributeError. База рекурсииПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились. для деревьев — всегда «пустой узел». Запустите код и добавьте проверку на None.