Создание дерева

Один из способов создания дерева – это вложенная структура из функторов и аргументов, как в предыдущем примере. Однако в общем случае Пролог создает дерево путем вычисления. На каждом шаге пустое поддерево заменяется непустым в процессе унификации (сопоставления по аргументам).

Создание дерева из одного узла путем присвоения обычных данных тривиально:

create_tree(N, tree(N, empty, empty)).

Здесь говорится: "Если N – данное, то tree(N, empty, empty) – это дерево из одного узла, содержащее его".

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

insert_left(X, tree(А, _, В), tree(А, X, В)).

Заметьте, что в этом предложении нет тела, т. е. нет четких шагов при его выполнении. Все, что должен сделать компьютер, – это соединить аргументы друг с другом в правильном порядке, – и работа закончена.

Предположим, что вы хотите вставить tree("Michael", empty, empty) в качестве левого поддерева для tree("Cathy", empty, empty). Чтобы это сделать, надо выполнить целевое утверждение:

insert_left(tree("Michael", empty, empty),

tree("Cathy", empty, empty),

T)

Тогда Т примет значение:

tree("Cathy", tree("Michael", empty, empty), empty).

Это дает способ построения дерева шаг за шагом.

Сортировка на основе дерева

После того, как дерево построено, можно легко переставить все его элементы в алфавитном порядке. Алгоритм для этого – вновь вариант поиска "сначала – вглубь":

1. Если дерево пустое, то ничего не делать.

2. Иначе, переставить все элементы левого поддерева, потом текущий элемент, затем все элементы правого поддерева.

Или на Прологе:

retrieve_all(empty). % Ничего не делать

retrieve_all(tree(Item, Left, Right)):-

retrieve_all(Left),

do_something_to (Item),

retrieve_all(Right).

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

Особенности ввода-вывода в языке Пролог.

Чтение символов

Системные предикаты get(X), get0(X), skip(X) служат для ввода символов с терминала пользователя. Коды символов различаются в зависимости от используемой реализации Пролога. В микрокомпью­терах в основном применяется код ASCII*, а в больших ЭВМ (таких, как ICL2900) - код EBDIC**.

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