Что такое бинарное дерево?

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

Ключевые характеристики:

• Каждый узел имеет указатель на значение (данные) и указатели на левого и правого потомков (могут быть пустыми).
• Существует корневой узел — верхний узел дерева, не имеющий предка.
• Листья — узлы, не имеющие потомков.
• Поддеревья — каждое поддерево корня бинарного дерева также является бинарным деревом.

Основные типы бинарных деревьев:

• Полное бинарное дерево: на каждом уровне за исключением, возможно, последнего, все узлы имеют двух потомков, а на последнем уровне все узлы сдвинуты влево.
• Совершенное бинарное дерево: все уровни полностью заполнены, каждый узел (кроме листьев) имеет двух потомков.