уровни, начиная с Уров
вывод( Дер, Уров, 0, Дальше), nl,
% Вывести вершины уровня Уров
Уров1 is Уров + 1,
уровни( Дер, Уров1, Дальше).
% Обработать следующие уровни
вывод( nil, _, _, _, _ ). вывод( д( Лев, X, Прав), Уров, ГлубХ, Дальше) :- Глуб1 is ГлубХ + 1, вывод( Лев, Уров, Глуб1, Дальше), % Вывод левого поддерева ( Уров = ГлубХ, !, % X на нашем уровне? write( X), Дальше = да; % Вывести вершину, продолжить write(' ') ), % Иначе - оставить место вывод( Прав, Уров, Глуб1, Дальше). % Вывод левого поддерева
макс1( U, V, М) :- % М = 1 + макс( U, V) U > V, !, М is U + 1; М is V + 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.