Else begin. While (Item<>nil) and (Item^.Value<>Key) do

Item: = fRoot;

While (Item< > nil) and (Item^.Value< > Key) do

if Key< Item^.Value

then Item: = Item^.Left // спуск по левой ветви

else Item: = Item^.Right; // спуск по правой ветви

Addr: = Item;

end;

end; // function tSearchTree.Addr

Метод, реализующий поиск по дереву с включением:

function tSearchTree.Search(Key: tValue): pItem;

// Поиск элемента с заданным ключом Key с включением

procedure IncKey(var Item: pItem); // рекурсивная процедура поиска

Begin

if Item= nil

then begin // элемента с ключом Key нет: включение его в качестве листа

Item: = New(pItem); Item^.Value: = Key;

Item^.Left: = nil; Item^.Right: = nil;

Result: = Item; Inc(fSize);

End

Else

if Key< Item^.Value then IncKey(Item^.Left) // поиск слева

Else

if Key> Item^.Value then IncKey(Item^.Right) // поиск справа

else Result: = Item; // элемент найден

end; // procedure IncKey

Begin

IncKey(fRoot);

end; // function tSearchTree.Search

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

ситуация 1: элемента с ключом Key нет в дереве, в этом случае дерево остается неизменным;

ситуация 2: элемент с ключом Key имеет не более одного потомка – после исключения ближайший потомок поднимается на его место;

ситуация 3: элемент с ключом Key имеет двух потомков, в этом случае исключаемый элемент нужно заменить самым правым элементом его левого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, предшествующий исключаемому в обходе слева направо. После исключения узла с двумя потомками дерево останется деревом поиска и в том случае, если заменить исключаемый элемент самым левым элементом его правого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, следующий за исключаемым в обходе слева направо.

Ниже приведено исходное дерево поиска (а). Дерево (б) получается из дерева (а) после исключения элемента 15 и замены его элементом 11 – самым правым элементом левого поддерева узла 15 (в процедуре обхода слева направо он предшествует узлу 15). Дерево (в) получается из дерева (а) после исключения элемента 15 и замены его элементом 18 – самым левым элементом правого поддерева узла 15 (в процедуре обхода следует за узлом 15).

(а) (б) (в)

procedure tSearchTree.Delete(Key: tValue);

// Поиск элемента с заданным ключом Key с исключением

procedure DelKey(var Item: pItem); // основная рекурсивная процедура

Var

DelItem: pItem; // указатель на исключаемый элемент

procedure Del(var Addr: pItem);

// Вспомогательная рекурсивная процедура. Возвращает адрес самого

// правого элемента левого поддерева удаляемого узла DelItem

Begin