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

Один из способов создания дерева - это запись ячеистой структуры

функторов и аргументов, как в предыдущем примере CH07EX09.PRO. Однако, в

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

тое поддерево заменяется непустым в процессе Прологовского объединения

(подбор по агрументам).

Создание дерева из одного узла присвоением исходного данного триви-

ально:

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

Здесь говорится: " Если N - данное, то tree(N, empty, empty) - это

дерево из одного узла, содержащее его".

Построение структуры дерева так же просто. Следующей процедуре нужны

три дерева в качестве аргументов. Она вставляет первое дерево в качестве

левого поддерева во второе дерево и результат этого присваивает третьему

дереву:

insert_left(X, tree(A, _, B), tree(A, X, B)).

Заметьте, что в этом предложении нет тела, то есть нет четких шагов

при его выполнении. Все, что должен сделать компьютер - это соединить ар-

гументы друг с другом в правильном порядке - и работа закончена.

Для примера предположим, что вы хотите вставить дерево ("Michael",

empty, empty) в качестве левого поддерева для дерева ("Cathy", empty,

empty). Чтобы это сделать, надо выполнить целевое утверждение

insert_left(tree("Michaelz", empty, empty),

tree("Cathy", empty, empty),

T)

и T немедленно примет значение:

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

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

показан в программе CH07EX10.PRO. В действительности, элементы, которые

надо добавить к дереву могут приходить с внешнего входа.

/* Программа CH07EX10.PRO */

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Простые процедуры построения дерева *

* create_tree(A, B) помещает A в поле данных одноузлового *

* дерева B *

* insert_left(A, B, C) вставляет A как левое поддерево B *

* и присваивает результат C *

* insert_right(A, B, C) вставляет A как правое поддерево *

* B и присваивает результат C *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

domains

treetype = tree(string, treetype, treetype) ; empty()

predicates

create_tree(string, treetype)

insert_left(treetype, treetype, treetype)

insert_right(treetype, treetype, treetype)

clauses

create_tree(A, tree(A, empty, empty)).

insert_left(X, tree(A, _, B), tree(A, X, B)).

insert_right(X, tree(A, B, _), tree(A, B, X)).

goal

/* Сначала создадим несколько одноузловых деревьев*/

create_tree("Charles", Ch),

create_tree("Hazel", H),

create_tree("Michael", Mi),

create_tree("Jim", J),

create_tree("Eleanor", E),

create_tree("Melody", Me),

create_tree("Cathy", Ca),

/* ...затем соединим их... */

insert_left(Ch, Mi, Mi2),

insert_right(H, Mi2, Mi3),

insert_left(J, Me, Me2),

insert_right(E, Me2, Me3),

insert_left(Me3, Ca, Ca2),

insert_right(Me3, Ca2, Ca3),

/* ...и печатаем результат. */

write(Ca3), nl.

Заметьте, что в Прологе нет возможности изменить значение переменной

после того как присвоение произошло. Поэтому в программе CH07EX10.PRO ис-

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

новое значение, требуется новая переменная. Но, обычно, большое число

имен переменных не нужно, так как в общем случае повторяющиеся процедуры

получают новые переменные, вызывая себя рекурсивно, и каждый вызов имеет

определенный набор переменных.