Задача про бинарное дерево - Prolog (227024)

Формулировка задачи:

Дана задача, которая строит бинарное дерево и выводит сумму значений всех вершин дерева. Не могу вывести дерево и вместо суммы вершин дерева нужно выводить их количество.

domains
tree=nil;t(integer,tree,tree)
 
predicates
n(tree,integer).
 
clauses
n(nil,0).
n(t(H,Left,Right),S):-n(Left,LeftSum),n(Right,RightSum),S=LeftSum+RightSum+H.
n(t(_,Left,Right),S):-n(Left,LeftSum),n(Right,RightSum),S=LeftSum+RightSum.
 
goal
n(t(5,t(3,t(7,nil,nil),nil),t(1,t(30,nil,nil),t(5,nil,nil))),S),write(S).

Решение задачи: «Задача про бинарное дерево»

Листинг программы

domains
tree=nil;t(integer,tree,tree)
 
predicates
n(tree,integer).
 
clauses
n(nil,0).
n(t(_,Left,Right),S):-n(Left,LeftSum),n(Right,RightSum),S=LeftSum+RightSum+1.
n(t(_,Left,Right),S):-n(Left,LeftSum),n(Right,RightSum),S=LeftSum+RightSum.
 
goal
n(t(5,t(3,t(7,nil,nil),nil),t(1,t(30,nil,nil),t(5,nil,nil))),S),write(S).

Объяснение кода листинга программы

Задача: реализация предиката n для вычисления суммы элементов в бинарном дереве.
Переменные: tree (nil или t(integer, tree, tree)), S (сумма элементов).
Домены: tree=nil; t(integer, tree, tree).
Правила:
- n(nil, 0).
- n(t(_, Left, Right), S) :- n(Left, LeftSum), n(Right, RightSum), S = LeftSum + RightSum + 1.
- n(t(_, Left, Right), S) :- n(Left, LeftSum), n(Right, RightSum), S = LeftSum + RightSum.
Цель: n(t(5, t(3, t(7, nil, nil), nil), t(1, t(30, nil, nil), t(5, nil, nil))), S), write(S).
Вывод: 46.