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

Рассмотрим следующий массив, который, как утверждается, представляет собой двоичное дерево:

[1, 2, 5, 6, -1, 8, 11]

Учитывая, что индекс со значением -1 указывает на корневой элемент, у меня возникают следующие вопросы:

a) Как это на самом деле представлено?

Должны ли мы следовать приведенным ниже формулам (источник по этой ссылке), чтобы вычислить дерево? Три простые формулы позволяют перейти от индекса родителя к индексу его детей и наоборот:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

Если использовать приведенные выше формулы, то индекс(корень) = 3, индекс(левый ребенок) = 7, чего не существует.

b) Важно ли знать, является ли оно полным двоичным деревом или нет?

9
задан musefan 24 November 2011 в 12:35
поделиться