добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-
больше( Y, X), % Ввести Х в левое поддерево
добавить( L, X, L1).
добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-
больше( X, Y), % Ввести Х в правое поддерево
добавить( R, X, R1).
добкор( nil, X, дер( nil, X, nil) ). % Ввести Х в пустое дерево
добкор( дер( L, Y, R), Х, дер( L1, Х, дер( L2, Y, R) )) :-
больше( Y, X),
добкор( L, X, дер( L1, X, L2) ).
добкор( дep( L, Y, R), X, дep( дep( L, Y, R1), X, R2) ) :-
больше( X, Y),
добкор( R, X, дер( R1, X, R2) ).
Рис. 9. 15. Внесение элемента на произвольный уровень двоичного справочника.
На рис. 9.15 показана программа для 'недетерминированного' добавления элемента в двоичный справочник.
Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию
добавить( nil, 3, Д1), добавить( Д1, 5, Д2),
добавить( Д2, 1, Д3), добавить( Д3, 6, Д),
добавить( ДД, 5, Д).
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
9. 4. Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель
write( Т)
хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа - пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.
Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).
Рис. 9. 16. (а) Обычное изображение дерева. (b) То же дерево,
отпечатанное процедурой отобр (дуги добавлены для ясности).
