Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 45

Предположим, что у нас есть числа от 1 до 100 в двоичном дереве поиска, и мы хотим найти число 55. Какая из следующих последовательностей НЕ МОЖЕТ быть последовательностью проверенных узлов?
(А) {10, 75, 64, 43, 60, 57, 55}
(В) {90, 12, 68, 34, 62, 45, 55}
(С) {9, 85, 47, 68, 43, 57, 55}
(D) {79, 14, 72, 56, 16, 53, 55}

Ответ: (с)
Объяснение: В BST правый потомок родителя должен быть больше, чем родитель, а левый потомок должен быть меньше, чем родитель, но в C после 47 68 идет с правой стороны, потому что он больше, чем parent, теперь все, что ниже этой точки, должно быть больше 47, но 43 появляется, что не удовлетворяет свойству BST.
Тест на этот вопрос

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

ВОРОТА | GATE IT 2006 | Вопрос 45

0.00 (0%) 0 votes