| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Процедура балансировки дерева [D7, XP]

inoc ©   (2007-04-19 10:35:00) 

Классическая задача создания идеально сбалансированного дерева.
Берем Вирта, оттуда функция (переведенная в 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;

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

---

inoc   (2007-04-19 14:30:00) [1]

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

---

MBo   (2007-04-19 13:18:00) [2]

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;

---

Наверх