Операция исключения из бинарного дерева.

При удалении узла дерево должно оставаться упорядоченным относительно ключа:

а) удаляется лист;

б) удаляется узел с одним потомком (потомок слева или справа);

в) удаляется узел с двумя потомками, но в левом потомке нет правого поддерева;

г) общий случай.

t:=t^.R_Son;

end;

if g^.R_Son=nil then begin

g:=t;

t:=t^.L_Son;

dispose(g);

end;

Случай а) является частным случаем этого алгоритма.

Случай в): r указывает на элемент, не имеющий правого поддерева.

g:=t;

dispose(g);

Procedure Get (x: integer; var t: ElPtr);

var g: ElPtr;

begin

if t=nil then {обработка исключительной ситуации, когда элемента с заданным ключом в дереве нет}

else if x>t^.key then Get(x, t^.R_Son)

else if x<t^.key then Get(x, t^.L_Son)

else begin

g:=t;

if g^.L_Son=nil then t:=g^.R_Son

else if g^.R_Son=nil then t:=g^.R_Son

else D(g^.L_Son); {найти r)

dispose(g);

end;

end;