Как устроено бинарное дерево

Бинарное дерево — это структура данных, где каждый узел имеет не более двух потомков (левый и правый).

Основные свойства:

• Корень (root) — начальный узел.
• Листья (leaves) — узлы без потомков.
• Глубина — длина пути от корня до узла.
• Высота — максимальная глубина дерева.

Пример реализации узла:

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

Виды бинарных деревьев:

1. Полное — все уровни заполнены, кроме последнего.
2. Сбалансированное — разница высот поддеревьев ≤ 1.
3. Двоичное дерево поиска (BST) — левые потомки меньше родителя, правые — больше.

Применение: поиск, сортировка, обходы (in-order, pre-order, post-order).