Определить высоту (глубину) дерева на Prolog

      Комментарии к записи Определить высоту (глубину) дерева на Prolog отключены

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 1 месяц назад.

  • Автор
    Сообщения
  • #2213

    questioner
    Участник

    Помогите решить лабораторную на Prolog.

    Нужно определить высоту бинарного дерева. Высота дерева в программировании — это наибольший путь от корня до листа. Дерево задано следующим образом:
    treetype = tree(integer, treetype, treetype); empty. Т.е. каждый узел хранит либо целое число и две ссылки на соседние узлы, либо является листом (пустым узлом)

    .

    Вложения:
  • #2260

    На каждом шаге функция должна вычислять высоты левого и правого поддерева, выбирать из них максимальную, в качестве результата выдавать на единицу увеличенное значение. Решение для пустого дерева очевидно и используется для окончания рекурсии.

    В таком алгоритме нам потребуется правило получения наибольшего из двух чисел (max):

    max(A, B, A):- A > B, !.
    max(_A, B, B).

    domains
      treetype = tree(integer, treetype, treetype); empty
    predicates
      tree_height(treetype, integer)
    clauses
      tree_height(empty, 0):-!.
      tree_height(tree(_Value, LeftSubtree, RightSubtree), Height):-
        tree_height(LeftSubtree, LeftSubtreeHeight),
        tree_height(RightSubtree, RightSubtreeheight), 
        max(LeftSubtreeHeight, RightSubtreeheight, MaxSubtreeHeight),
        Height = MaxSubtreeHeight + 1.

Для ответа в этой теме необходимо авторизоваться.