Количество вершин в бинарном дереве - 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.

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

  1. Задана структура бинарного дерева, в которой каждый узел имеет два потомка (левой и правой ветви) и значение (метку).
  2. Задана переменная int типа integer, которая представляет собой значение узла.
  3. Задана переменная tree типа tree, которая представляет собой ссылку на структуру бинарного дерева.
  4. Задана функция nil, которая представляет собой пустой узел (лист) бинарного дерева.
  5. Задана процедура counter(tree, int), которая подсчитывает количество вершин в бинарном дереве.
  6. Задано правило counter(nil, 0), которое определяет начальное значение для подсчета вершин в пустом дереве.
  7. Задано правило counter(bt(_, L, R), N) :- counter(L, NL), counter(R, NR), N = NL + NR + 1), которое рекурсивно определяет количество вершин в непустом узле как сумму количества вершин в левом и правом поддеревьях, плюс один.
  8. В цели (задаче) задано выражение counter(bt(5, bt(1, nil, nil), bt(10, bt(7, nil, nil), nil)), N), которое описывает дерево с 7 вершинами.
  9. В цели (задаче) также задано выражение write(N), которое выводит результат подсчета вершин на экран.
  10. В цели (задаче) также задано выражение nl, которое выводит символ новой строки на экран.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.636 из 5