Программирование на языке Пролог для искусственного интеллекта
Шрифт:
Рис. 9.13. Удаление элемента из двоичного справочника.
Трудным моментом здесь является введение X на место корня. Сформулируем эту операций в виде отношения
где X — новый элемент, вставляемый вместо корня в Д, а Д1 — новый справочник с корнем X.
Рис. 9.14. Внесение X в двоичный справочник в качестве корня.
Ответ мы получим, если учтем следующие ограничения на L1, L2:
• L1 и L2 — двоичные справочники;
• множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L;
• все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.
Отношение, которое способно наложить все эти ограничения на L1, L2, — это как раз и есть наше отношение
Те же самые ограничения применимы к R1, R2:
На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.
Рис. 9.15. Внесение элемента на произвольный уровень двоичного справочника.
Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:
9.4. Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры
хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.
Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).
Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой
Давайте определим процедуру
так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:
Для того, чтобы отобразить непустое дерево T, необходимо:
(1) отобразить правое поддерево дерева T с отступом вправо на расстояние H;
(2) отпечатать корень дерева T;
(3) отобразить левое поддерево дерева T с отступом вправо на расстояние H.
Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру
печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами
На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.
Рис. 9.17. Отображение двоичного дерева.
9.14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья — справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.