Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 14

Рассмотрим следующее вложенное представление бинарных деревьев: (XYZ) указывает, что Y и Z являются левым и правым дополнительным напряжением, соответственно, узла X. Обратите внимание, что Y и Z могут быть NULL или дополнительно вложенными. Что из следующего представляет допустимое двоичное дерево?
(А) (1 2 (4 5 6 7))

(В) (1 (2 3 4) 5 6) 7)
(С) (1 (2 3 4) (5 6 7))
(D) (1 (2 3 NULL) (4 5))

Ответ: (с)
Пояснение: Чтобы решить этот вопрос, нам нужно взглянуть на две вещи:
1) В двоичном дереве узел может иметь не более 2 дочерних элементов.
2) Чтобы построить бинарное дерево из приведенных выше последовательностей, сначала нужно сработать с самой внутренней скобкой.

В варианте A: (4 5 6 7) есть, что говорит, что у узла 4 есть три дочерних элемента, что неверно для двоичного дерева, а также в вопросе определен только (XYZ), то есть узел X может иметь не более 2 детей, которые будут корнями поддеревьев Y и Z.

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

ВОРОТА | GATE-CS-2000 | Вопрос 14

0.00 (0%) 0 votes