Дерево — связный граф без циклов. На нём построены BST, кучи, файловые системы, организационные иерархии.
Дерево — связный граф без циклов. Главное свойство: между любыми двумя вершинами существует ровно один путь. Деревья лежат в основе BST, куч, файловых систем, XML и DOM.
V, E, корень, высота, глубина
У каждого узла не более двух детей
В бинарном дереве каждый узел имеет не более двух детей: левого и правого.
Количество узлов в полном бинарном дереве высоты h:
Пример: при h=3 → N = 2⁴ − 1 = 15 узлов.
В BST для каждого узла выполняется правило: все ключи в левом поддереве меньше, в правом — больше. Это позволяет находить элемент за O(h), где h — высота.
Если дерево сбалансировано, h ≈ log₂N, и поиск работает за O(log N). Если вырождено (как список), то за O(N).
Куча — почти полное бинарное дерево, в котором значение в каждом узле ≤ (min-куча) или ≥ (max-куча) значений его потомков. Используется в пирамидальной сортировке и приоритетной очереди.
Обход в ширину (BFS) — посещаем все узлы уровня level L перед level L+1. Использует очередь. Применяется для поиска кратчайшего пути в дереве, печати уровень-за-уровнем.
Обход в глубину (DFS) — идём как можно глубже по одной ветке, потом возвращаемся. Три варианта: pre-order (корень→лево→право), in-order (лево→корень→право), post-order (лево→право→корень). Использует стек (или рекурсию).
3 классических способа обойти бинарное дерево
Корень → Левый → Правый
Левый → Корень → Правый
Левый → Правый → Корень
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None: return BSTNode(key)
if key < root.key: root.left = bst_insert(root.left, key)
else: root.right = bst_insert(root.right, key)
return root
def bst_search(root, key):
while root:
if key == root.key: return root
root = root.left if key < root.key else root.right
return None
def bst_inorder(root, res=[]):
if root:
bst_inorder(root.left, res)
res.append(root.key)
bst_inorder(root.right, res)
# Сборка дерева:
root = None
for k in [5, 3, 7, 1, 4, 6, 8]:
root = bst_insert(root, k)
seq = []; bst_inorder(root, seq)
print(seq) # [1, 3, 4, 5, 6, 7, 8]
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.