9.4. Отображение деревьев
9.4. Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель
write( T)
хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.
Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).
![](https://storage.yandexcloud.net/wr4img/278325_107__62.png)
Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой отобр (дуги добавлены для ясности).
Давайте определим процедуру
отобр( T)
так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:
Для того, чтобы отобразить непустое дерево T, необходимо:
(1) отобразить правое поддерево дерева T с отступом вправо на расстояние H;
(2) отпечатать корень дерева T;
(3) отобразить левое поддерево дерева T с отступом вправо на расстояние H.
Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру
отобр2( T, H)
печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:
отобр( T) :- отобр2( T, 0).
На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.
отобр( T) :-
отобр2( T, 0).
отобр2( nil, _ ).
отобр2( дер( L, X, R), Отступ) :-
Отступ2 is Отступ + 2,
отобр2( R, Отступ2),
tab( Отступ), write( X), nl,
отобр( L, Отступ2).
Рис. 9.17. Отображение двоичного дерева.
Упражнение
9.14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья — справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.