Отображение деревьев

Как и все объекты данных в языке Prolog, бинарное дерево Т можно непосредст­венно вывести на внешнее устройство с помощью процедуры write. Но цель write! T)

выводит лишь всю информацию, но не позволяет графически отобразить фактиче­скую структуру дерева. Но задача воссоздания на бумаге фактической структуры де­рева из терма Prolog, который представляет это дерево, может оказаться довольно утомительной. Поэтому часто возникает необходимость получить такую распечатку дерева, чтобы она графически показывала его структуру.

Ниже описан относительно простой метод отображения деревьев в такой форме. Весь его секрет состоит в том, чтобы дерево было отображено как растущее слева на­право, а не сверху вниз, как обычно изображаются деревья. Дерево разворачивается влево, чтобы его корень стал крайним левым элементом, а листья сдвигаются вправо. Такой метод изображения деревьев демонстрируется на рис. 9.10.

Определим процедуру show! T)

для вывода дерева Т в форме, показанной на рис. 9.10. Эта процедура действует по описанному ниже принципу.

	Чтобы вывести	на внешнее	устройство непустое дерево Т,	необходимо выпол-
нить следующие действия.
1.	Вывести правое стояние и.	поддерево	Т	обозначенное	отступом	вправо	на	некоторое	рас-
2.	Вывести корень	Т.
3.	Вывести левое стояние Н.	поддерево	Т,	обозначенное	отступом	вправо	на	некоторое	рас-

206 Часть I. Язык Prolog

t.l

левое

поддерево

Рис. 9.10. Различные методы изображения деревьев: а) обычное изображение дерева; б) то же дерево, распечатанное процедурой show {дуги добавлены для наглядности )

Расстояние отступа Н, которое может быть выбрано соответствующим образом, представляет собой дополнительный параметр процедуры вывода деревьев. После введения параметра Н получим процедуру show2t Т, Н)

для отображения дерева ? с отступом на К. пробелов от левого поля. Процедуры show и show2 связаны между собой следующим отношением: show! Т) :- shov;2( Т, 0) .

Законченная программа, в которой применяются отступы на 2 пробела, показана в листинге 9,7. Принцип выполнения вывода в таком формате можно легко приспо­собить для отображения деревьев других типов.