Деревья относятся к рекурсивным структурам данных (Рис.1). Важно, чтобы каждая ветвь дерева сама являлась деревом, поэтому структура рекурсивна.

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

Турбо Пролог позволяет определить рекурсивные типы, в которых указатели создаются и обрабатываются автоматически. Например, можно определить дерево следующим образом:

domains
treetype = tree (string, treetype, treetype)

Эта декларация говорит о том, что дерево записывается как функтор tree (дерево), аргументами которого являются строка и два других дерева.
Но, это не совсем верно, так как нет способа закончить рекурсию. В действительности дерево не может распространяться до бесконечности. Некоторые узлы не имеют связи с другими деревьями. Прологе нет доступа к указателям. Решение состоит в том, чтобы определить два типа деревьев — обычное и пустое. Это достигается тем, что дерево может иметь одно из двух описаний tree (дерево) с тремя аргументами или empty (пусто) без аргументов.
domains
treetype = tree (string, treetype, treetype); empty

Заметьте, что названия tree (функтор у которого три аргумента) и empty (функтор без аргументов) создаются программистом, и ни одному из них нет предопределенного в Прологе значения. С тем же успехом можно использовать xxx и yyy.
Вот как дерево на рис. 1 будет описано в прологовской программе:

tree («Катя»,
tree («Миша»,
tree («Вова», empty, empty),
tree («Лида», empty, empty)),
tree («Люда»,
tree («Зина», empty, empty),
tree («Петя», empty, empty)))

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

tree («Катя»,
tree («Миша»,
tree («Вова», empty, empty),
tree («Лида», empty, empty)),
tree («Люда»,
tree («Зина», empty, empty),
tree («Петя», empty, empty)))