Скачать: CL | DM;

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

← →
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;

---

← →
inoc ©   (2007-04-19 14:30) [2]

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.03 c