Бинарное дерево — это структура данных, состоящая из узлов, где каждый узел имеет не более двух дочерних узлов: левого и правого.
Основные понятия:
- Корень (Root): Самый верхний узел.
- Узел (Node): Базовый элемент дерева, содержит данные и ссылки на дочерние элементы.
- Родительский узел (Parent node): Узел, имеющий дочерние узлы.
- Дочерний узел (Child node): Узел под родительским узлом.
- Лист (Leaf): Узел, не имеющий дочерних узлов.
- Глубина (Depth): Расстояние от корня до узла.
- Высота (Height): Максимальная глубина от корня до самого глубокого листа.
Типы бинарных деревьев:
- Полное бинарное дерево (Full Binary Tree): Каждый узел имеет либо 0, либо 2 дочерних узла.
- Идеальное бинарное дерево (Perfect Binary Tree): Все внутренние узлы имеют ровно 2 дочерних узла, и все листовые узлы находятся на одной глубине.
- Сбалансированное бинарное дерево (Balanced Binary Tree): Разница между глубиной левого и правого поддерева для каждого узла