Рубрики

ВОРОТА | GATE-CS-2015 (набор 2) | Вопрос 20

Бинарное дерево T имеет 20 листьев. Число узлов в T, имеющих двух детей, равно
(А) 18
(Б) 19
(С) 17
(D) Любое число от 10 до 20

Ответ: (Б)
Объяснение:

Сумма всех степеней = 2 * | E |.

Здесь рассматривая дерево как k-арное дерево:


Sum of degrees of leaves + Sum of degrees for Internal Node except root + Root's degree = 2 * (No. of nodes - 1).

Putting values of above terms,

L + (I-1)*(k+1) + k = 2 * (L + I - 1)

L + k*I - k + I -1 + k = 2*L + 2I - 2

L + K*I + I - 1 = 2*L + 2*I - 2

K*I + 1 - I = L

(K-1)*I + 1 = L

Given k = 2, L=20

==> (2-1)*I + 1 = 20
==> I = 19
==> T has 19 internal nodes which are having two children.

Посмотрите Лемму Рукопожатия и Интересные Свойства дерева для доказательства.

Это решение предоставлено Анил Сайкришна Деварасетты
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 2) | Вопрос 20

0.00 (0%) 0 votes