Программирование на языке Пролог для искусственного интеллекта

  % X и Y помещаются в разные списки
 разбить( 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, M2, Д2, М3, Д3) ):-
  % Вершина имеет три поддерева
 больше( M2, Элем), !,
  % Элемент не во втором и не в третьем поддереве
 внутри( Элем, Д1);      % Поиск в первом поддереве
 больше( M3, Элем), !,   % Элемент не в третьем поддереве
 внутри( Элем, Д2);      % Поиск во втором поддереве
 внутри( Элем, Д3).      % Поиск в третьем поддереве

10.3

avl( Дер) :-
 аvl( Дер, Глуб).  % Дер является AVL-деревом глубины Глуб
avl( nil, 0).      % Пустое дерево - AVL -дерево глубины 0
avl( д( Лев, Кор, Прав), Г) :-
 avl( Лев, ГЛ),
 avl( Прав, ГП),
 ( ГЛ is ГП; ГЛ is ГП + 1; ГЛ is ГП - 1),
  % Глубины поддеревьев примерно совпадают
 макс( ГЛ, ГП, Г).
макс1( U, V, М) :- % М = 1 + макс( U, V)
 U > V, !, М is U + 1;
 М is V + 1.