Назад | Содержание| Вперёд 9. 4. Отображение деревьев Так же, как...

Назад | Содержание| Вперёд

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

Так же, как и любые объекты данных в Прологе,двоичное дерево Т может быть непосредственновыведено на печать при помощи встроеннойпроцедуры write. Однако цель

write( Т)

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

Существует относительно простой способ этосделать. Уловка состоит в том, чтобы изображатьдерево растущим слева направо, а не сверху вниз,как обычно. Дерево нужно повернуть влево такимобразом, чтобы корень стал его крайним слеваэлементом, а листья сдвинулись вправо (рис. 9.16).

Рис. 9. 16. (а) Обычное изображение дерева. (b) То же дерево,

отпечатанное процедурой отобр (дугидобавлены для ясности).

Давайте определим процедуру

отобр( Т)

так, чтобы она отображала дерево в форме,показанной на рис. 9.16. Принцип работы этойпроцедуры:

Для того, чтобы отобразить непустое дерево Т,необходимо:

(1) отобразить правоеподдерево дерева Т с отступом вправо нарасстояние Н;

(2) отпечатать кореньдерева Т;

(3) отобразить левоеподдерево дерева Т с отступом вправо нарасстояние Н.

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

отобр2( Т, Н)

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

отобр( Т) :- отобр2( Т,0).

На рис. 9.17 показана программа целиком. В этойпрограмме предусмотрен сдвиг на 2 позиции длякаждого уровня дерева. Описанный принципотображения можно легко приспособить длядеревьев других типов.

отобр( Т) :-

отобр2( Т, 0).

отобр2( nil, _ ).

отобр2( дер( L, X, R),Отступ) :-

Отступ2 is Отступ + 2,

отобр2( R, Отступ2),

tab( Отступ), write( X), nl,

отобр( L, Отступ2).

Рис. 9. 17. Отображениедвоичного дерева.

Упражнение

9. 14. Наша процедураизображает дерево, ориентируя его необычнымобразом: корень находится слева, а листья -справа. Напишите (более сложную) процедуру дляотображения дерева, ориентированного обычнымобразом, т.е. с корнем наверху и листьями внизу.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление