Этот вопрос проверяет понимание структуры бинарного дерева и умение работать с геометрическими прогрессиями.
В полностью заполненном бинарном дереве каждый уровень полностью заполнен. Если высота дерева равна N (корень на уровне 0), то количество узлов равно 2^(N+1) - 1. Это связано с тем, что на каждом уровне количество узлов удваивается. Формула легко выводится как сумма геометрической прогрессии.
Полностью заполненное бинарное дерево — это идеальный пример структуры с регулярным ростом числа узлов.
Определение: Perfect бинарное дерево — бинарное дерево, в котором у каждого внутреннего узла есть ровно два потомка, а все листья находятся на одном уровне.
Рассмотрим уровни дерева:
Уровень 0 (корень): 1 узел
Уровень 1: 2 узла
Уровень 2: 4 узла
Уровень k: 2^k узлов
Если высота дерева N, то уровни идут от 0 до N.
Общее число узлов — это сумма:
1 + 2 + 4 + ... + 2^N
Это геометрическая прогрессия, сумма которой:
2^(N+1) - 1
Для N = 2:
Уровни: 1 + 2 + 4
Всего: 7 узлов
Для N = 3:
1 + 2 + 4 + 8 = 15
Формула 2^(N+1) - 1 позволяет быстро считать узлы без построения дерева.
Она часто используется при анализе сложности алгоритмов на деревьях.
