Prolog
Шрифт:
разбить( L, L1, L2).
9. 9
(а) двдерево( nil).
двдерево( д( Лев, Кор, Прав) ) :-
двдерево( Лев),
двдерево( Прав).
9. 10
глубина( пусто, 0).
глубина( д( Лев, Кор, Прав), Г) :-
глубина( Лев, ГЛ),
глубина( Прав, ГП),
макс( ГЛ, ГП, МГ),
Г is МГ + 1.
макс( А, В, А) :-
А >= В, !.
макс( А, В, В).
9. 11
линеаризация( nil, [ ]).
линеаризация( д( Лев, Кор, Прав), Спис) :-
линеаризация( Лев, Спис1),
линеаризация( Прав, Спис2),
конк( Спис1, [Кор | Спис2], Спис).
9. 12
максэлемент( д( _, Кор, nil), Кор) :- !.
% Корень - самый правый элемент
максэлемент( д( _, _, Прав,), Макс) :-
% Правое поддерево непустое
максэлемент( Прав, Макс).
9. 13
внутри( Элем, д( _, Элем, _ ), [ Элем]).
внутри( Элем, д( Лев, Кор, _ ), [Кор | Путь]) :-
больше( Кор, Элем),
внутри( Элем, Лев, Путь).
внутри( Элем,д( _, Кор, Прав), [Кор | Путь]) :-
больше( Элем, Кор),
внутри( Элем, Прав, Путь).
9. 14
% Отображение двоичного дерева, растущего сверху вниз
% Предполагается, что каждая вершина занимает при печати
% один символ
отобр( Дер) :-
уровни( Дер, 0, да).
% Обработать все уровни
уровни( Дер, Уров, нет) :- !.
% Ниже уровня Уров больше нет вершин
уровни( Дер, Уров, да) :-
% Обработать все уровни, начиная с Уров
вывод( Дер, Уров, 0, Дальше), nl,
% Вывести вершины уровня Уров
Уров1 is Уров + 1,
уровни( Дер, Уров1, Дальше).
% Обработать следующие уровни
вывод( nil, _, _, _, _ ).
вывод( д( Лев, X, Прав), Уров, ГлубХ, Дальше) :-
Глуб1 is ГлубХ + 1,
вывод( Лев, Уров, Глуб1, Дальше),
% Вывод левого поддерева
( Уров = ГлубХ, !,
% X на нашем уровне?
write( X), Дальше = да;
% Вывести вершину, продолжить
write(' ') ),
% Иначе - оставить место
вывод( Прав, Уров, Глуб1, Дальше).
% Вывод левого поддерева
Глава 10
10. 1
внутри( Элем, л( Элем)). % Элемент найден в листе
внутри( Элем, в2( Д1, М, Д2) ):-
% Вершина имеет два поддерева
больше( М, Элем), !, % Вершина не во втором поддереве
внутри( Элем, Д1); % Поиск в первом поддереве
внутри( Элем, Д2). % Иначе - во втором поддереве
внутри( Элем, в3( Д1, М2, Д2, М3, Д3) ):-
% Вершина имеет три поддерева
больше( М2, Элем), !,
% Элемент не во втором и не в третьем поддереве
внутри( Элем, Д1); % Поиск в первом поддереве
больше( М3, Элем), !, % Элемент не в третьем поддереве
внутри( Элем, Д2); % Поиск во втором поддереве