Удаление узла из дерева
Задача удаления узла в сформированном дереве решается в следующем порядке: 1. поиск удаляемого узла 2. анализ найденного узла Поиск удаляемого узла осуществим с помощью двух переменных-указателей: q – поискового, указывающего на найденный узел, и v, отстающего от него на уровень и всегда указывающего на корень удаляемого узла: Var root, q, v, r : TRebro; poisk: Integer; искомое число (узел) flag: 0..1; флаг поиска: 1 – узел найден, 0 – не найден Методика удаления узла будет зависеть от того, какого типа этот узел: a. лист b. узел с одним поддеревом, c. узел с двумя поддеревьями. Добавим в нашу программу процедуру удаления заданного узла. Сначала найдем заданный узел - на него будет указывать ссылка 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;
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|