Алгоритм
Рассмотрим алгоритм в котором вместо удаляемого узла ставится самый левый узел правого поддерева. Удалим узел с номером 150, тогда на его место станет элемент под номером 152, т.к. он является самым левым из правого поддерева.
Введем следующие обозначения:
P - рабочий указатель
Q - указатель отстающий от Р на один шаг
V - указатель на элемент, который будет замещать удаляемый узел
T - указатель, отстает от V на один шаг
S - указатель, опережает V на один шаг
Пример программы удаления элементов бинарного дерева
(Псевдокод)
Q=nil
P=Tree
While (P<>nil)and(K(P)<>key)do {поиск узла с нужным ключем}
If key<K(P) then P=Left(P)
Else P=Right(P)
EndIf
EndWhile
If P=nil then "Ключ не найден" {проверка если такого элемента нет}
Return {выход}
EndIf
If Left(P)=nil then V=Right(P) {если левая ссылка равна nil
Else
If Right(P)=nil then V=Left(P)
Else
GetNode(P)
T=P
V=Right(P) S = Left(V)
While S <> nil {поиск самого }
T = V {левого эл-нта}
V = S {правого поддерева}
S = Left(V)
EndWhile
If T <> P then
"V-не сын"
Left(T) = Right(V)
Right(V)= Right(P)
EndIf
Left(V) = Left(P)
If Q = nil then
"p - корень"
Tree = V
Return
EndIf
If P = Left(Q) then
Left(Q) = V
Else
Right(Q)= V
EndIf
EndIf
EndIf
FreeNode(P)
Return
Иллюстрация процесса удаления узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).
Конечный вариант дерева после удаления
