Процедура балансировки дерева

← →
inoc © (2007-04-19 10:35) [0]

Классическая задача создания идеально сбалансированного дерева.
Берем Вирта, оттуда функция (переведенная в Delphi):

Function prootBLns(L:integer):Ttree;
Var p:Ttree; m,m1:integer;
begin
if (L=0) then P:=Nil
else begin
m:=L div 2;
m1:=l-m-1;
New(p); P^.Inf:=mas[m];
P^.A1:=ProotBLns(m);
P^.A2:=ProotBLns(m1);
end;
Result:=p;
end;

краткое пояснения: mas - массив элементов, отсортированных по возрастанию ключа.

Результат - узлы выбираются по нескольку раз (дублируются), а некоторые просто "пролетают". Может где пропустил чего?

В методе - вот такая функция, вызов prootBLns(1,n)
Function prootBLns(K,L:Word):Ttree;
Var p:Ttree; m:Word;
begin
if K>L then P:=Nil
else begin
m:=K+L div 2;
New(p); P^.Inf:=a[m];
P^.A1:=ProotBLns(K,m);
P^.A2:=ProotBLns(m+1,L);
end;
Result:=p;
end;

Результат - переполнение.

← →
MBo © (2007-04-19 13:18) [1]

Function prootBLns(StartIdx, EndIdx):Ttree; Var p:Ttree; m:Word; begin if StartIdx > EndIdx then P := Nil else begin Middle := (StartIdx + EndIdx) div 2; New(p); P^.Inf := a[Middle]; P^.Left := ProotBLns(StartIdx, Middle - 1); P^.Left := ProotBLns(Middle + 1, EndIdx); end; Result:=p; end;

Работает, спасибо!

Процедура балансировки дерева Найти похожие ветки