Количество вершин в бинарном дереве - Prolog
Формулировка задачи:
Задача: Вычислить количество вершин в бинарном дереве. Пытался сделать, но до конца с синтаксисом пролог при работе с деревьями не разобрался,выдавала ошибки. Заранее благодарен!
Решение задачи: «Количество вершин в бинарном дереве»
textual
Листинг программы
domains int=integer tree = bt(int, tree, tree); nil predicates counter(tree,int) clauses counter(nil,0). counter(bt(_,L,R),N) :- counter(L,NL), counter(R,NR), N=NL+NR+1. goal counter(bt(5,bt(1,nil,nil),bt(10,bt(7,nil,nil),nil)),N), write(N), nl.
Объяснение кода листинга программы
- Задана структура бинарного дерева, в которой каждый узел имеет два потомка (левой и правой ветви) и значение (метку).
- Задана переменная
intтипаinteger, которая представляет собой значение узла. - Задана переменная
treeтипаtree, которая представляет собой ссылку на структуру бинарного дерева. - Задана функция
nil, которая представляет собой пустой узел (лист) бинарного дерева. - Задана процедура
counter(tree, int), которая подсчитывает количество вершин в бинарном дереве. - Задано правило
counter(nil, 0), которое определяет начальное значение для подсчета вершин в пустом дереве. - Задано правило
counter(bt(_, L, R), N) :- counter(L, NL), counter(R, NR), N = NL + NR + 1), которое рекурсивно определяет количество вершин в непустом узле как сумму количества вершин в левом и правом поддеревьях, плюс один. - В цели (задаче) задано выражение
counter(bt(5, bt(1, nil, nil), bt(10, bt(7, nil, nil), nil)), N), которое описывает дерево с 7 вершинами. - В цели (задаче) также задано выражение
write(N), которое выводит результат подсчета вершин на экран. - В цели (задаче) также задано выражение
nl, которое выводит символ новой строки на экран.