Рубрики

Структуры данных | Бинарные деревья | Вопрос 8

Количество листовых узлов в укорененном дереве из n узлов, каждый из которых имеет 0 или 3 дочерних узла, равно:
(А) н / 2
(B) (n-1) / 3
(С) (н-1) / 2
(D) (2n + 1) / 3

Ответ: (Д)
Объяснение: Пусть L будет числом листовых узлов, а I будет числом внутренних узлов, тогда для вышеупомянутого дерева справедливо следующее соотношение (подробнее см. Вопрос 3 этого поста )

  L = (3-1)I + 1 = 2I + 1

Общее количество узлов (n) является суммой листовых узлов и внутренних узлов

  n = L + I

После решения вышеупомянутых двух мы получаем L = (2n + 1) / 3
Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Бинарные деревья | Вопрос 8

0.00 (0%) 0 votes