Бинарное дерево из массива

[Nicko_mt]

Доброго времени суток. Возник вопрос.Стояла задача построить дерево посредством массивов
1.каждая родительская вершина может иметь не более двух потомков;
2.для каждой родительской вершины "левый" потомок меньше нее по весу, а "правый" – больше;
3.для каждой родительской вершины каждый из элементов ее "левого" поддерева меньше нее по весу, а "правого" - больше.

Т.е.если у нас 10, 3, 7, 2, 1, 4, 5, 13, 8, 6, 14, 9, 11, 15, 12.
То дерево
8
4 12
2 6 10 14
1 3 5 7 9 1 13 15
Частично я задачу решил но запутался в измышлениях
По логике здесь формула количества вершин 2^n-1
И сначала надо отсортировать
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Выбрать середину
Потом также выбрать середины у оставшихся кусков
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Далее привожу код который составил.Правда слишком всё сложно и вышло составить только левую ветвь и то элементы которые закономерности не поддаются например 5 и 7 прикрепить не удалось.Может быть как то можно облегчить алгоритм?

uses crt;
const count = 15;
var i,koren,k,k1,kt:integer;
a:array[1..count] of integer;
procedure left(index:integer);
begin
  if (k=1) then exit
else
  k:=(index div 2)-1+1;
  for i:=0 to index  do begin
  if (((index div 2)-1)+1 =i)
  then writeln(a[i], ' sleva ot ',a[index] );kt:=kt+1;
end;
writeln(k);
  for i:=0 to index do begin
  if (((k div 2))+k =i)
  then writeln(a[i], ' sprava ot ',a[k] );kt:=kt+1;
  end;
  writeln(k);
  left(k);
  end;
procedure right(index:integer);
begin
  if (k1=count) then exit
else
  k1:=(index div 2)+index;
  for i:=index to count  do begin
    if (((index div 2)+index =i))
  then writeln(a[i], ' sprava ot ',a[index] );
  end;
  writeln(k1);
  right(k1);
  end;

begin
writeln('Vvod massiva:');
for i:=1 to count do
begin
write('Elem #',i,': ');
readln(a[i]);
end;
for i:=0 to count do
if ((count div 2)+1 = i) then begin
writeln('Koren- ',a[i]);
koren:=a[i];
end;
left(koren);




for i:=1 to count do
begin
write(a[i],' ');
end;
readln;

end.

Заранее благодарен.

[igor_kz]

В общем не обязательно необходимо сортировать начальный массив.
Информацию, которую храним для каждой вершины, это ее значение, ссылка на левого потомка, и на правого. При необходимости можно хранить дополнительные поля(например высоту).
Далее:
Первый элемент массива определяем корнем всего дерева. И для каждого следующего элемента, просто спускаемся по дереву(начиная с корня), и если значение которое хотим добавить больше значения корня, спускаемся вправо, иначе влево, и т.д. пока не упремся в никуда(т.е. некуда дальше спускаться, мы в листе дерева). Сюда как раз таки и вставляем необходимое значение.

Вставка элемента работает за О(H), где H - высота дерева.
А высота дерева - это H = log(N), тут N - количество вершин в дереве.
И количество вершин не обязательно 2^n-1, дерево может быть и не полным.