Рубрики

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

В полном k-арном дереве каждый внутренний узел имеет ровно k дочерних элементов или не имеет дочерних элементов. Количество листьев в таком дереве с n внутренними узлами составляет:
(А) нк
(B) (n — 1) k + 1
(С) n (k — 1) + 1
(D) n (k — 1)

Ответ: (с)
Объяснение: Для k-арного дерева, где у каждого узла есть k дочерних элементов или нет дочерних, выполняется следующее соотношение
L = (k-1) * n + 1

Где L — количество листовых узлов, а n — количество внутренних узлов.

Давайте посмотрим, например, следующее

             o
        /    |    \
      o      o      o
   / | \          / | \
  o  o  o        o  o  o
                  / | \
                 o  o  o

k = 3
Number of internal nodes n = 4
Number of leaf nodes = (k-1)*n  + 1
                     = (3-1)*4 + 1
                     = 9 

Тест на этот вопрос

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

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

0.00 (0%) 0 votes