Удаление узла из дерева

Задача удаления узла в сформированном дереве решается в следующем порядке:

1. поиск удаляемого узла

2. анализ найденного узла

Поиск удаляемого узла осуществим с помощью двух переменных-указателей: q– поискового, указывающего на найденный узел, иv,отстающего от него на уровень и всегда указывающего на корень удаляемого узла:

Var root, q, V, r : tRebro;

poisk: Integer; искомое число (узел)

flag: 0..1; флаг поиска: 1 – узел найден, 0 – не найден

Методика удаления узла будет зависеть от того, какого типа этот узел:

1. лист

2. узел с одним поддеревом,

3. узел с двумя поддеревьями.

Добавим в нашу программу процедуру удаления заданного узла. Сначала найдем заданный узел - на него будет указывать ссылка q:

Write(‘Что удалить: ’);

ReadLn(poisk); ввод удаляемого узла

If (poisk = 0) если это 0,

Then Break; то выходим из цикла удаления

q := root; поисковик q – в корень дерева

v := q; v отстает на шаг

flag := 0; еще ничего не найдено

While (q <> nil) Do пока не дошли до листа:

Begin

If (q^.Data = poisk) Then если нашли удаляемый узел:

Begin

flag:= 1; флаг поиска – на 1

Break; и выходим из цикла поиска

End; {If}

v:=q; если еще не нашли: подтянули ссылку v к поисковику q

If (poisk < q^.Data) и сделали шаг по дереву на уровень ниже

Then q:=q^.Left

Else q:=q^.Right;

End; {While}

Если удаляемый узел найден (flag=1),то начинается его анализ:

1. если этолист– то безболезненно его удаляем (q– указатель на удаляемый узел,v– указатель на его предка):

If (q^.Left = Nil) And (q^.Right = Nil) Then это лист

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=Nil то вместо него Nil,

Else v^.Right:=Nil; иначе Nil - справа от предка

Dispose(q); освобождаем от него память

{на продолжение}

End;

2. если у него слева– ничего нет, асправа- поддерево:

If (q^.Left = Nil) And (q^.Right <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Right то слева вместо него - правое поддерево узла q,

Else v^.Right:=q^.Right; иначе справа вместо него - правое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

3. если у него справа– ничего нет, аслева- поддерево:

If (q^.Right = Nil) And (q^.Left <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Left то слева вместо него -левое поддерево узла q,

Else v^.Right:=q^.Left; иначе справа вместо него - левое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

4. если у него и слева и справа–поддеревья. В этом случае нужно:

• сделать шаг влевои идти до конца все времянаправоили

• сделать шаг вправои идти до конца все времяналево.

q – ссылка на удаляемый узел,

r– ссылка на узел, который поставим на место удаляемого,

v– ссылка на предка узлаr.

Найденным узлом rзаменим удаляемый узелq:

If (q^.Right <> Nil) And (q^.Left <> Nil) Then

Begin

v:=q; подтягиваем указатель v к q

r:=q^.Right; ссылкой r делаем шаг вправо

от удаляемого узла

While (r^.Left <> Nil) Do идем все время налево до конца

Begin

v:=r; подтягиваем указатель v к r

r:=r^.Left; и делаем по дереву шаг влево

End; {While}

q^.Data:=r^.Data; помещаем вместо удаляемого узла q найденный самый левый на этом пути,

If (r^.Right = Nil)

Then v^.Left:=Nil а вместо него подвешиваем Nil

Else v^.Left:=r^.Right; или его правое поддерево

Dispose(r); освобождаем память от найденного узла

End;