Поиск записи в дереве( find ).

ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).

Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом.

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

• 1) найдена вершина, содержащая ключ, равный ключу X;
• 2) в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

В первом случае возвращается указатель на найденную вершину. Во втором - указатель на звено, где остановился поиск, (что удобно для построения дерева ). Реализация функции Find приведена в программном примере 6.2.

{=== Программный пример 6.2. Поиск звена по ключу === } Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean; { где k - ключ, d - корень дерева, rez - результат } Var p,g: TreePtr; b: boolean; Begin b:=false; p:=d; { ключ не найден } if d <> NIL then repeat q: =p; if p^.key = k then b:=true { ключ найден } else begin q:=p; { указатель на отца } if k < p^.key then p:=p^.left { поиск влево } else p:=p^.right { поиск вправо} end; until b or (p=NIL); Find:=b; rez:=q; End; { Find }