Удаление из бинарного дерева Опции

[biba]

Такая вот задачка.
Эта программа удаляет заданный узел. Но она не удаляет узел вместе с поддеревями , а только один. А мне нужно, чтобы удаляла вместе поддеревями . Т.е. чтобы и узел пропал, и все, что после него. Как это сделать. И можно ли что-то сделать прямо в этой программе, чтобы покороче.

Код

 function FIND(Root:ref; kl3:integer; var T{указатель
на удаляемый элемент},Parent{его предок}:ref):boolean;
begin T:=Root; while T<> nil do
begin if kl3=T^.key then begin FIND:=true; exit end;
Parent:=T;{запомнить указатель перед спуском}
if kl3<T^.key then T:=T^.Left else T:=T^.Right; end;
FIND:=False; end;

procedure DEL (var Root:ref; kl3:integer);  {без поддеревьев}
var T:ref; {удаляемый узел} Parent:ref; {предок удаляемого узла}
    Q:ref; {узел,заменяющий удаляемый} fl:boolean;

function SPUSK (var T:ref):ref; {спуск по дереву}
var Q:ref;{узел,заменяющий удаляемый} prev:ref; {предок Q}
begin Q:=T^.Right;
if Q^.Left=nil then Q^.Left:=T^.Left {1} {см стр 148 Павловской}
else begin {2} repeat
prev:=Q; Q:=Q^.Left; until Q^.Left=nil; Q^.Left:=T^.Left; {3}
prev^.Left:=Q^.Right; {4} Q^.Right:=T^.Right; {5} end;
SPUSK:=Q; end;

begin {ищем ключ}
if not FIND (Root,kl3,T,Parent) then begin textcolor(15); gotoxy(25,7);
writeln('Такого элемента нет');
textcolor(8); gotoxy(20,11);
writeln('Нажмите любую клавишу для продолжения');
readkey; exit; end;

if T^.Left=nil then Q:=T^.Right {7} else
if T^.Right=nil then Q:=T^.Left {8} else Q:=SPUSK (T); {9}
if T=Root then Root :=Q   {10}  else {11}
if kl3 < parent^.key then parent^.Left:=Q else parent^.Right:=Q;
DISPOSE (T); {12} end;

[Altair]

http://forum.pascal.dax.ru/forum/index.php...indpost&p=28334
Там разве нет??

Но она не удаляет узел вместе с поддеревями  , а только один.

Что-то написанно криво ...
Я что-то ен пойму смысла ...

Сообщение отредактировано: volvo - 17.01.2005 9:53

[biba]

http://forum.pascal.dax.ru/forum/index.php...indpost&p=28334
Там разве нет??

Что-то написанно криво ...
Я что-то ен пойму смысла ...

Там нет.

А смысл такой. Например нужно удалить узел с ключом 10. А после него Идут еще 8,15,17 и т.д. Вот эта программа удалит ключ 10. А остальные переставит, чтобы сохранилось дерево. А нужно, чтобы и 8 и 15 и 17 и т.д. тоже удалились. Надеюсь объяснила понятно

Сообщение отредактировано: volvo - 17.01.2005 9:54

[Altair]

Ну и объедини в цикл или в рекурсию, чтобы после удаления, процедура еще дальше удаляла.

[zx1024]

Что-то типа

Код

procedure Del (T : Ref);
begin
 if T.Left = nil then
   if T.Right = nil then
     Dispose (T)
   else
   begin
     Del (T.Right);
     T.Right := nil
   end
 else
 begin
   Del (T.Left);
   T.Left := nil
 end
end;

А в проге написать

Код

if Find (Root,1024,T1,Parent) then
 Del (T1);

И главное - не включать в прогу процедуру SPUSK.
Из FIND Parent тоже лучше убрать, тем более, что он не всегда определен (когда kl3 это вершина дерева)

Сообщение отредактировано: zx1024 - 18.09.2004 2:11