Давайте определим процедуру
отобр( Т)
так, чтобы она отображала дерево в форме, показанной на рис. 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. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.
Посмотреть ответ
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
9. 5. Графы
9. 5. 1. Представление графов
Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество
В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Например, графы,
