New(T);

with T^ do

Begin

inf.slovo:=slovo; inf.count_sl:=1;

L:=nil; R:=nil

End

End

Else

if slovo < T^.inf.slovo then

Slovar(T^.L, slovo)

Else

if slovo > T^.inf.slovo then

Slovar(T^.R, slovo)

else T^.inf.count_sl:=T^.inf.count_sl+1

end; { Slovar }

Упражнение 4.4. Описать нерекурсивную логическую функцию, проверяющую, входит ли заданный элемент в дерево поиска.

Упражнение 4.5. Описать нерекурсивную процедуру или функцию подсчета числа вхождений заданного элемента в дерево поиска.

4.3 Исключение из дерева поиска

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

1) Узла с заданным значением в дереве нет.

2) Узел с заданным значением имеет не более одного потомка, т.е. удаляемый узел или терминальная вершина (лист), или вершина с одним
потомком.

3) Узел с заданным значением имеет двух потомков.

Трудности возникают в случае 3), так как удаляемый узел нужно заменить либо на самый правый узел его левого поддерева, либо на самый левый узел его правого поддерева, причем они должны иметь не более одного потомка.

Пример 4.4. Описать процедуру исключения узла с заданным значением x из дерева поиска T.

procedure Delete(var T: Tree; x: integer);

var q: Tree;

procedure Del(var p: Tree);

Begin

if p^.R <> nil then Del(p^.R)

Else

Begin

q^.inf:=p^.inf; q:=p;

p:=p^.L

End

end; { Del }

Begin

if T = nil then { элемента в дереве нет }

Else

if x < T^.inf then Delete(T^.L, x)

Else

if x > T^.inf then Delete(T^.R, x)

Else

begin { исключение узла T^ }

q:=T;

if q^.R = nil then T:=q^.L

Else

if q^.L = nil then T:=q^.R

else Del(q^.L);

{ освобождение памяти, выделенной для размещения узла q^ }