Глава 7. добавить( Элемент, Список) :-

7.2

добавить(Элемент, Список):-

var(Список),!,

% Переменная Список представляет пустой список

Список = [Элемент | Хвост].

добавить(Элемент, [ _ | Хвост]):-

добавить(Элемент, Хвост).

принадлежит(X, Список):-

var(Список),!,

% Переменная Список представляет пустой список,

% поэтому X не может ему принадлежать

fail.

принадлежит(X, [X | Хвост]).

принадлежит(X, [ _ | Хвост]):-

принадлежит(X, Хвост).

Глава 8

8.2

добавить_в_конец(L1-[Элемент | Z2], Элемент, L1 - Z2).

8.3

обратить(А - Z, L - L):-

% Результатом является пустой список,

% если A-Z представляет пустой список

А == Z,!.

обратить([X | L] - Z, RL - RZ):-

% Непустой список

обратить(L - Z, RL - [X | RZ].

Глава 9

9.1

список([]).

список([ _ | Хвост]):-

список(Хвост).

9.2

принадлежит(X, X затем ЧтоУгодно).

принадлежит(X, Y затем Спис):-

принадлежит(X, Спис).

9.3

преобр([, ничего_не_делать).

преобр([Первый | Хвост], Первый затем Остальные):-

преобр(Хвост, Остальные).

9.4

преобр([, ПустСпис, _, ПустСпис).

% Случай пустого списка

преобр([Первый | Хвост], НовСпис, Функтор, Пустой):-

НовСпис =.. [Функтор, Первый, НовХвост],

преобр(Хвост, НовХвост, Функтор, Пустой).

9.8

сорт1([], []).

сорт1([X], [X]).

сорт1(Спис, УпорСпис):-

разбить(Спис, Спис1, Спис2),

% Разбить на 2 прибл. равных списка

сорт1(Спис1, Упор1),

сорт1(Спис2, Упор2),

слить(Упор1, Упор2, УпорСпис).

% Слить отсортированные списки

разбить([], [], []).

разбить([X], [X], []).

разбить([X, Y | L], [X | L1], [Y | L2]):-

% 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, Дальше).

% Вывод левого поддерева