Бинарные деревья - Prolog (227089)

Формулировка задачи:

Бинарные деревья задаются с помощью тернарного функтора tree(Left,Root,Right), где Root - элемент, находящийся в вершине, а Left и Right - соответственно левое и правое поддерево. Пустое дерево изображается атомом nil. Следующий терм является примером более сложного дерева tree(nil, 5, tree(nil, 6, tree(tree(nil, 8, nil), 10,nil))). Определите отношение ordered(+Tree), выполненное, если дерево Tree является упорядоченным деревом целых чисел, т.е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любого элемента в правом поддереве. Вышеприведенное в качестве примера дерево является упорядоченным. Указание. Можно использовать вспомогательные предикаты ordered_left(+X, +Tree) и ordered_right(+X, +Tree), которые проверяют, что X меньше (больше) всех чисел в вершинах левого (правого) поддерева дерева Tree и дерево Tree - упорядоченно.

Решение задачи: «Бинарные деревья»

Листинг программы

domains
treetype = tree(integer, treetype, treetype); nil
 
predicates
isOrdered(treetype)
 
clauses
isOrdered(nil).
isOrdered(tree(_,nil,nil)).
isOrdered(tree(Root,tree(VLeft,LL,LR),tree(VRight,RL,RR))) :- Root > VLeft, Root <= VRight, isOrdered(LL), 
isOrdered(LR),isOrdered(RL),isOrdered(RR). 
isOrdered(tree(Root,tree(VLeft,_,_),tree(_,_,_))) :- Root <= VLeft, fail.
isOrdered(tree(Root,tree(_,_,_),tree(VRight,_,_))) :- Root > VRight, fail.

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

В начале кода определяются два домена: treetype и nil.
Затем определяется predicate isOrdered(treetype).
Далее идут три утверждения (clauses), которые описывают условие, при котором дерево считается упорядоченным.
Условие для nil-узла: isOrdered(nil).
Условие для листового узла: isOrdered(tree(_,nil,nil)).
Условие для внутреннего узла: isOrdered(tree(Root,tree(VLeft,LL,LR),tree(VRight,RL,RR))) :- Root > VLeft, Root <= VRight, isOrdered(LL), isOrdered(LR),isOrdered(RL),isOrdered(RR).
Условие для нечетного дерева: isOrdered(tree(Root,tree(VLeft,,),tree(,,_))) :- Root <= VLeft, fail.
Условие для четного дерева: isOrdered(tree(Root,tree(,,),tree(VRight,,_))) :- Root > VRight, fail.
Код проверяет, является ли дерево упорядоченным, путем проверки порядка элементов в каждом поддереве.
Если дерево не является упорядоченным, то оно считается неупорядоченным и проверка прекращается.
Код не использует термины левое, правое или среднее для определения порядка элементов в поддереве, вместо этого он сравнивает значения Root, VLeft и VRight.
Код проверяет только элементы в левом и правом поддеревьях, а не в среднем поддереве.
Если дерево является упорядоченным, то оно считается упорядоченным по возрастанию.
Код не проверяет, является ли дерево полным или отсутствуют ли в нем узлы.
Код не проверяет, является ли дерево сбалансированным или несбалансированным.
Код не использует рекурсию для проверки порядка элементов в поддереве.
Код не использует циклы для проверки порядка элементов в поддереве.
Код проверяет только порядок элементов в поддереве, а не их значения.
Код не использует дополнительные переменные для хранения промежуточных значений.
Код не использует ввод/вывод для получения или отправки данных.