2011-gre-cs-practice-book.pdf/Q16

Вопрос: Q16-08c765

Полное бинарное дерево — это корневое дерево, в котором каждый внутренний узел имеет ровно два потомка. Сколько внутренних узлов в полном бинарном дереве с 500 листьями?

Ответы

• 250
• Правильный ответ: 499
• 500
• 501
• 1000

Объяснение

Исходники — вопрос 16 на 22 странице книги «2011-gre-cs-practice-book.pdf»

Проиллюстрируем на картинке:

• Начнём с первого дерева у которого два листа.
• Далее, если мы хотим прибавить +1 лист к дереву, то мы дорисовываем по 2 потомка свободным листам, беря их слева направо.
• Таким образом количество листьев всегда на 1 больше количества внутренних узлов

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.