Алгоритм
Рассмотрим алгоритм вставки узла в бинарное дерево.
Вставим узел с номером 150, тогда он станет правым сыном узла с номером 120, т.к. он является большим по значению узла с номером 120, но меньше значения узла головы дерева.
P - рабочий указатель
Q - указатель отстающий от Р на один шаг
V - указатель на элемент, который будет вставлен в бинарное дерево .
Иллюстрация процесса вставки узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).
Конечный вариант дерева после вставки :
Программа
Псевдокод Паскаль
Q=nil Q=nil
P=Tree P=Tree
While (P<>nil) do While (P<>nil) do
Q=P Begin
If key=k(P) then Q=P;
search=P If key=P^.k then
return Begin
EndIf search:=P;
If key<k(P) then exit;
P=left(P) End;
else If key<P^.k then
P=right(P) P:=P^.left;
EndIf else
EndWhile P:=P^.right;
V=maketree(key,rec) End;
If key<k(Q) then V=maketree(key,rec)
else If key<Q^.k then
Right(Q)=V Q^.left:=V
EndIf else
search=V Q^.right:=V;
Return search:=V
