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, Дальше).
                            % Вывод левого поддерева