Деревья - как типы данных

Рекурсивные типы популяризовались Никлаусом Виртом в книге "Алгорит-

мы + Структуры Данных = Программы. (Вирт изобрел Паскаль - не Пролог -

около двадцати лет назад.) Он не применял в Паскале рекурсивные типы, но

определил, какими они должны быть. Если бы в Паскале были рекурсивные ти-

пы, то можно было бы определить дерево наподобие следующего:

type tree = record /* Некорректно в Паскале! */

name: string[80];

left,

right: tree

end;

На естественный язык этот фрагмент переводится так: "Дерево состоит

из имени (Name), которое есть строка (string), а так же левого и правого

поддеревьев, которые тоже являются деревьями".

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

и записав:

type treeptr = ^tree;

tree = record

name: string[80];

left,

right: treeptr

end;

Заметьте существенное различие: этот фрагмент имеет дело с представ-

лением дерева в памяти, а не с собстенно структурой дерева. Он обращается

с деревом как с объектом, состоящим из узлов, каждый из которых содержит

некоторые данные и указатели на два других узла.

Турбо Пролог позволяет определить действительно рекурсивные типы, в

которых указатели создаются и обрабатываются автоматически.

Например, можно определить дерево следующим образом:

domains

treetype = tree(string, treetype, treetype)

Эта декларация говорит о том, что дерево записывается как функтор

tree (дерево), аргументами которого являются строка и два других дерева.

Но, это не совсем верно, так как нет способа закончить рекурсию. В

действительности дерево не может распространяться до бесконечности. Неко-

торые узлы не имеют связи с другими деревьями. В Паскале это можно выра-

зить, присвоив некоторым указателям специальное нулевое значение, но в

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

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

жет иметь одно из двух описаний tree (дерево) с тремя аргументами или

empty (пусто) без аргументов.

domains

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

Заметьте, что названия tree (функтор у которого три аргумена) и

empty (функтор без аргументов) создаются программистом, и ни одному из

них нет предопределенного в Прологе значения. С тем же успехом можно ис-

пользовать xxx и yyy.

Вот как дерево на рис. 7.1 будет описано в прологовской программе:

tree("Cathy",

tree("Michael",

tree("Charles", empty, empty),

tree("Hazel", empty, empty)),

tree("Melody",

tree("Jim", empty, empty),

tree("Eleanor", empty, empty)))

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

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

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

способом:

tree("Cathy",

tree("Michael", tree("Charles", empty, empty),

tree("Hazel", empty, empty)),

tree("Melody", tree("Jim", empty, empty),

tree("Eleanor", empty, empty)))

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

данных.