|
В бинарном упорядоченном дереве удалить узел с заданным значением ключевого поля. |
|
4. В бинарном упорядоченном дереве удалить узел с заданным значением ключевого поля.
Опишем рекурсивную процедуру, которая будет учитывать наличие требуемого элемента в дереве и количество потомков этого узла. Если удаляемый узел имеет двух потомков, то он будет заменен самым большим значением ключа в его левом поддереве, и только после этого он будет окончательно удален.
Procedure Delete1(x : Byte; var t : TreeLink);
Var p : TreeLink;
Procedure Delete2(var q : TreeLink);
Begin
If q^.right <> nil then Delete2(q^.right)
Else
Begin
p^.inf := q^.inf;
p := q;
q := q^.left;
End;
End;
Begin
If t = nil then
Writeln('искомого элемента нет')
Else if x < t^.inf then
Delete1(x, t^.left)
Else if x > t^.inf then
Delete1(x, t^.right)
Else
Begin
P := t;
If p^.left = nil then
t := p^.right
Else
If p^.right = nil then
t := p^.left
Else
Delete2(p^.left);
End;
End.
|
