Рубрики

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

Схема хранения двоичных деревьев в массиве X заключается в следующем. Индексирование X начинается с 1 вместо 0. Корень хранится в X [1]. Для узла, хранящегося в X [i], левый дочерний элемент, если он есть, сохраняется в X [2i], а правый дочерний элемент, если он есть, в X [2i + 1]. Чтобы иметь возможность хранить любое двоичное дерево в n вершинах, минимальный размер X должен быть. (GATE CS 2006)

(A) log2n
(B) n
(С) 2n + 1
(D) 2 ^ n — 1

Ответ: (Д)
Объяснение: Для двоичного дерева с перекосом вправо число узлов будет 2 ^ n — 1. Например, в нижнем двоичном дереве узел «A» будет храниться в индексе 1, «B» в индексе 3, «C» в индекс 7 и «D» на индекс 15.

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

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

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

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

0.00 (0%) 0 votes