Вывод дерева на Prolog

      Комментарии к записи Вывод дерева на Prolog отключены

Помечено: , ,

В этой теме 0 ответов, 1 участник, последнее обновление  questioner 7 мес., 1 неделя назад.

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

    questioner
    Участник

    Мы рассмотрим вывод элементов дерева в виде списка чисел (в линейном виде), а также вывод дерева с отображением его структуры — «расти оно будет слева-направо».

    Вывод дерева в виде списка

    Если вы пишите на Turbo/Visual Prolog, то сначала надо описать тип дерева в разделе domains (на SWI Prolog это делать не надо, как и объявление функции в секции predicates):

    domains
      element = integer
      node_d = node(node_d, node_d, element); null

    Мы говорим, что в дереве будут храниться элементы целого типа, а узел дерева представляет собой либо структуру, хранящую ссылку на левое и правое поддеревья (также являющиеся узлами дерева) и значение, либо метку (null, но можно было дать любое другое имя), означающую что узел является листом (не хранит значение).

    Наша функция должна принимать дерево, которое задается узлом самого верхнего уровня (вершиной дерева), в разделе predicates пишем:
    print_tree_left_top_right(node_d)

    Наконец, описываем саму функцию вывода в секции clauses:

      print_tree_left_top_right(null):-!.
      print_tree_left_top_right(node(Left, Right, TopValue)):-
      	print_tree_left_top_right(Left),
      	write(TopValue), write(" "), 
      	print_tree_left_top_right(Right).

    Если узел является листом, то выводить ничего не требуется — в нем ведь нет значения. В противном случае мы можем получить из узла левое и правое поддеревья, а также хранимое значение, которые можем вывести в любом удобном нам порядке. Поддеревья выводятся рекурсивно.

    left-right-print-tree-example

    В нашем коде выводятся сначала элементы левого поддерева, а затем — правого. В связи с этим, если дерево является упорядоченным, то элементы будет выведены в порядке возрастания. Вместо функции вывода (write) могла бы использоваться любая другая функция, выполняющая обработку значения узла. При этом узлы были бы также обработаны в порядке возрастания, кроме того, мы могли бы обработать их в противоположном порядке просто выполнив сначала обработку правого поддерева, а затем — левого.

    вывод дерева слева-направо

    В ряде случаев требуется отображать структуру дерева, мы будем «рисовать» дерево слева-направо, т.е. слева у нас будет корень, а справа поддеревья. При выводе узла его нужно «сдвинуть» вправо в соответствии с номером уровня, на котором он расположен в дереве.

    Так для такого дерева:

    Мы получим следующий вывод:

    Исходный код такого решения:

    domains
      treetype = tree(integer, treetype, treetype); empty
    predicates
      print_tree(treetype, integer)
      print_spaces(integer)
    clauses
      print_tree(empty, _Depth):-!.
      print_tree(tree(TopValue, Left, Right), Depth):-
        SubtreesDepth = Depth + 1,
        print_tree(Left, SubtreesDepth),
        print_spaces(Depth), write(TopValue), write("<"), nl,
        print_tree(Right, SubtreesDepth).
        
      print_spaces(SpaceNumber):-
      	SpaceNumber <= 0, !;
      	write("\t"),
      	TailSpaceNumber = SpaceNumber - 1,
      	print_spaces(TailSpaceNumber).
     

    Функция print_spaces выводит заданное количество пробелов для «перемещения значения» на заданный уровень иерархии. Функция вывода дерева отличается от рассмотренной ранее тем, что в процессе вывода рассчитывается текущая глубина узла.

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