Если данные организованы как структура дерева, алгоритм поиска сводится к алгоритму, просматривающему все узлы дерева. Для ведения поиска существуют два основных алгоритма поиска: поиск в глубину и поиск в ширину.
Поиск в глубину. При поиске в глубину каждая ветвь дерева просматривается слева направо.
Для двоичных деревьев алгоритм поиска имеет простую рекурсивную структуру (рис. 7.1):
Рис. 7.1 — Схема поиска по двоичному дереву
DEPTHFIRST: procedure(TREE);
declare 1 TREE,
2 KEY,
2 ARGUMENT, /* данные */
2 RightSon, /* ноль, если нет сына*/
2 LeftSon; /* ноль, если нет сына */
if TREE = null then return;
if текущий узел не KEY then do;
call DEPTHFIRST(LtftSon);
call DEPTHFIRST(RightSon);
end;
end DEPTHFIRST;
Заметим, что если дерево упорядочено таким образом, что LeftSon имеет ключ, величина которого меньше, чем значение корневого узла, а величина ключа для RightSon больше, чем значение корневого узла, то такой алгоритм аналогичен алгоритму двоичного поиска.
Поиск в ширину. Это алгоритм поиска, при котором просматривается каждый уровень в направлении сверху вниз (рис. 7.2).
Рис. 7.2 — Поиск в ширину
При таком алгоритме параллельного поиска быстро находятся кратчайшие ветви дерева. В общем виде алгоритм имеет структуру:
BREADTHFIRST: procedure(solution);
declare 1 TREE,
2 ARGUMENT, /* данные */
2 SONS(N); /* произвольные деревья */
declare (solution, NextStep) set of TREE;
/* переход вниз для каждого уровня */
do while (solution ¹ 0);
NextStep = {TREE.SONS(I) для всех I и TREE
в solution};
call BREADTHFIRST(NextStep);
end;
end BREADTHFIRST;
Поиск в ширину очень популярен при решении задачи о лабиринте.
Поиск с возвратом. Для многих алгоритмов часто требуется перебор возможных вариантов решения задачи. Один из таких способов перебора называется поиском с возвратом.
Алгоритм:
Вызвать первую часть;
do while (не окончится);
вызвать следующую часть;
do while (нет возможности продолжить);
Вернуться на предыдущий уровень;
Проверить возможность альтернативного решения
для этого уровня;
end;
end;
Алгоритм поиска в глубину является примером поиска с возвратом:
Начать с корневого узла;
do while (существуют не просмотренные узлы);
Перейти к узлу «левый сын», если возможно;
Иначе перейти к узлу «правый брат»;
do while (нет узлов «левый сын» и «правый брат);
Перейти к узлу «отец»;
Перейти к узлу «правый брат», если можно;
end;
end;