Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
source_examples.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
307 Кб
Скачать
☆

Пример 11.4. Подсчет количества листьев (узлов без сыновей)

Предикат будет иметь два параметра. Входной - исходное дерево , выходной - количество листьев дерева , находящегося в первом параметре.

Так как в пустом дереве нет вершин, в нем нет и вершин, являющихся листьями . Это первый базис рекурсии. Второй базис будет заключаться в очевидном факте, что дерево , состоящее из одной вершины, имеет ровно один лист . Шаг: для того, чтобы посчитать количество листьев дерева , нужно просто сложить количество листьев в левом и правом поддереве.

/* в пустом дереве листьев нет */

tree_leaves(nil,0).

/* в дереве с одним корнем - один лист */

tree_leaves(tr(_, nil, nil),1):- !.

tree_leaves(tr(_,L,R),N):-

/* N1 - количество листьев в левом поддереве */

tree_leaves(L, N1),

/* N2 - количество листьев в правом поддереве */

tree_leaves(R, N2),

/* Находим сумму в левом и правом поддереве */

N is N1 + N2.

?- tree_leaves(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).

N = 3

Пример 11.5. Подсчет суммы чисел в вершинах дерева

Предикат будет иметь два аргумента. Первый - исходный список, второй - сумма чисел, находящихся в вершинах дерева , расположенного в первом аргументе.

Идея реализации будет очень простой и немного похожей на подсчет количества вершин. Базис рекурсии: сумма элементов пустого дерева равна нулю, потому что в пустом дереве нет элементов. Чтобы подсчитать сумму значений, находящихся в вершинах непустого дерева , нужно сложить сумму элементов, хранящихся в левом и правом поддереве, и не забыть добавить корневое значение.

/* в пустом дереве вершин нет */

tree_sum(nil, 0).

tree_sum(tr(X,L,R),N):-

/* N1 - сумма элементов левого поддерева */

tree_sum(L, N1),

/* N2 - сумма элементов правого поддерева */

tree_sum(R, N2),

/* складываем N1, N2 и корневое значение */

N is N1+N2+X.

% ?- tree_sum(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).

N = 17

Пример 11.6. Предикат, вычисляющий высоту дерева

Высота дерева - это наибольшая длина пути от корня дерева до его листа . Предикат будет иметь два параметра. Первый (входной) - дерево , второй (выходной) - высота дерева , помещенного в первый параметр.

Базис рекурсии будет основан на том, что высота пустого дерева равна нулю. Шаг рекурсии - на том, что для подсчета высоты всего дерева нужно найти высоты левого и правого поддеревьев, взять их максимум и добавить единицу (учесть уровень, на котором находится корень дерева ). Предикат max (или max2), вычисляющий максимум из двух элементов, был разработан нами еще в третьей лекции. Воспользуемся им при вычислении высоты дерева .

Получается следующее.

/* Высота пустого дерева равна нулю */

tree_height(nil, 0).

tree_height(tr(_,L,R),D) :-

tree_height(L,D1), /* D1 - высота левого поддерева */

tree_height(R,D2), /* D2 - высота правого поддерева */

max(D1,D2,D_M), /* D_M - максимум из высот левого и правого поддеревьев */

D is D_M+1. /* D - высота дерева, получается увеличением D_M на единицу*/

?- tree_height(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).

N = 3 ;

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]