Двоичный справочник на Prolog

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

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

    questioner
    Участник

    Помогите написать на Visual Prolog программу по заданию:
    создайте предикат, переписывающий дерево в двоичный справочник.

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

  • #3060

    Чтобы решить задачу нужно сначала реализовать функцию добавления элемента в двоичный справочник:

      insert_bst(Value, null, node(null, null, Value)):-!.
      insert_bst(Value, node(Left, Right, TopValue), node(NewLeft, Right, TopValue)):-
      	Value < TopValue, !, 
      	insert_bst(Value, Left, NewLeft).
      insert_bst(Value, node(_Left, Right, TopValue), node(_Left, NewRight, TopValue)):-
      	insert_bst(Value, Right, NewRight).

    Функция принимает добавляемое значение, вершину дерева (в которое производится добавление) и возвращает в качестве третьего аргумента вершину дерева (в которое выполнена вставка значения).

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

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

    На картинке показан пример вставки значений в дерево и результат вывода дерева слева-направо:
    insert_bst_prolog

    Теперь, чтобы преобразовать произвольное дерево в двоичный справочник нам достаточно выполнить обход этого дерева в любом порядке (слева-направо или справа-налево) и для каждого узла вызвать функцию вставки в справочник:

      tree_to_bst(null, Bst, Bst).
      tree_to_bst(node(LeftTree, RightTree, TopTreeValue),  BstBuffer, Bst):-
      	insert_bst(TopTreeValue, BstBuffer, BstWithTop),
      	tree_to_bst(LeftTree, BstWithTop, BstWithTopAndLeft),
      	tree_to_bst(RightTree, BstWithTopAndLeft, Bst).

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