Бинарные деревья - Prolog (226801)

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

Помогите, пожалуйста! Visual Prolog Даны число N, число M и список, элементы которого — непустые бинарные деревья с числами в качестве вершин. Для каждого такого дерева найти количество вершин, значения которых равны «0». Из полученных результатов сформировать список и вывести его. Затем через пробел вывести количество элементов в нём, лежащих в диапазоне от N до M включительно. Например: если дано "2 5 [bt(0,no,bt(0,no,no)),bt(3,bt(0,no,no),bt(2,no,no))]", ответом будет "[2,1] 1".

Решение задачи: «Бинарные деревья»

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

domains
bt = bt(integer, bt, bt); no
 
 
predicates
zero_count(bt,integer)
 
clauses
zero_count(no,0).
zero_count(bt(N,L,R),C) :- N=0, zero_count(L,NL), zero_count(R,NR), C=NL+NR+1.
zero_count(bt(N,L,R),C) :- N<>0, zero_count(L,NL), zero_count(R,NR), C=NL+NR.

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

domains - определение типа данных для переменной bt. В данном случае это бинарное дерево, которое может содержать целочисленные значения.
predicates - определение функции-предиката zero_count, которая принимает два аргумента: бинарное дерево и целочисленное значение.
clauses - определение правил (условий) для функции-предиката zero_count. В данном случае есть два правила: для случая, когда значение листового узла равно 0, и для случая, когда значение листового узла отлично от 0.
В первом правиле для листового узла со значением 0, функция zero_count рекурсивно вызывается для левого и правого поддеревьев, а затем к результату добавляется 1.
Во втором правиле для листового узла со значением, отличным от 0, функция zero_count рекурсивно вызывается для левого и правого поддеревьев, а затем к результату добавляется сумма результатов вызовов для левого и правого поддеревьев.