На этом шаге мы рассмотрим, как можно найти вершину в дереве.
Пусть X - элемент, который нужно найти. Следуя рекурсивному определению дерева, заметим, что:
- если X - это корень дерева, то считаем, что X уже найден, иначе
- если X меньше, чем корень, то искать X в левом поддереве, иначе
- искать в правом поддереве;
- если дерево пустое, то поиск терпит неудачу (третий аргумент становится равным 1).
Запишем это рассуждение на Прологе.
in (X, tr(_ ,X, _), 0).
in (_, tr (nil, _, nil), 1):-!.
in (X, tr (L, K, _), H):-
X<K,
in (X, L, H).
in (X, tr (_, K, R), H):-
X>K,
in (X, R, H).
Если третий аргумент - 1, то элемент не найден, если 0 - найден.
На следующем шаге мы рассмотрим, как можно добавить вершину в дерево.
