Ответ в теме: Двоичный справочник на Prolog

      Комментарии к записи Ответ в теме: Двоичный справочник на 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).