Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 65

В двоичном дереве с n узлами каждый узел имеет нечетное число потомков. Каждый узел считается своим потомком. Какое количество узлов в дереве имеет ровно один дочерний элемент?
(А) 0
(Б) 1
(С) (н-1) / 2
(D) n-1

Ответ: (А)
Объяснение: упомянуто, что у каждого узла есть нечетное число потомков, включая сам узел, поэтому у всех узлов должно быть четное число потомков 0, 2, 4 и так далее. Это означает, что каждый узел должен иметь 0 или 2 дочерних элемента. Таким образом, не будет узла с 1 дочерним элементом. Следовательно, 0 является ответом.

Ниже приведены несколько примеров.

       a
    /    \
   b      c


      a
    /   \
   b     c  
  /  \
 d    e

Такое двоичное дерево представляет собой полное двоичное дерево (двоичное дерево, в котором каждый узел имеет 0 или 2 дочерних элемента).

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

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

ВОРОТА | GATE CS 2010 | Вопрос 65

0.00 (0%) 0 votes