Prolog - Checking if a binary tree is ordered or not
-
14-04-2021 - |
Question
I want to write a program in Prolog that confirms if a b-tree of integers is ordered or not. The order goes from smaller to greater. This is what I've written so far but I do not reach any solid work. Does someone know how to do that?
Domains
element=integer
tree=a(tree,element,tree);void
Predicates
nondeterm ordre(tree)
Clauses
order(a(_,Node,a(_,Node2,_))):-Node<Node2.
order(a(Esq,Node,Dre)) :-
order(Esq),
write(Node),nl,
order(Dre).
Goal
order(a(a(void,1,void),2,a(a(void,3,void),4,a(void,6,void)))).
Huge Thanks.
Solution
domains
element = integer
arbre = a (arbre, element, arbre) ; buit
predicates
nondeterm ordenat (arbre)
nondeterm ordenat2 (arbre, element)
clauses
ordenat2 (a (buit, E, buit), E).
ordenat2 (a (buit, E, R), MR) :-
ordenat2 (R, MR),
E<MR.
ordenat2 (a (L, E, buit), E) :-
ordenat2 (L, ML),
ML<E.
ordenat2 (a (L, E, R), MR) :-
ordenat2 (L, ML), ML<E,
ordenat2 (R, MR), E<MR.
ordenat (A) :-
ordenat2 (A, _).
goal
B=a (a (a (buit, 1, buit), 2, a (buit, 3, buit)), 4, a (a (buit, 5, buit), 6, a (buit, 7, buit))),
ordenat (B)
.
Result: yes
OTHER TIPS
Using the same same tree structure as before (the atom btree
denoting an empty tree; the structure btree(Key,Left,Right)
denoting a non-empty tree, something like this should do you:
An empty tree is ordered by definition
is_ordered( btree ).
A non-empty tree is ordered if
- its left children are ordered and their keys are less than that of the current node
its right children are ordered and their keys are greater than that of the current node
is_ordered( btree( K , L , R ) ) :- is_ordered( L < K ) , is_ordered( R > K ) .
By definition, an empty tree is less than any specified key value and also greater than any specified key value.
is_ordered( btree < K ). is_ordered( btree > K ).
A non-empty tree is less than a specified key value if
- its key is less than the specified key, and
it is itself ordered
is_ordered( btree(K1,L,R) < K ) :- K1 < K , is_ordered( btree(K1,L,R) ) .
A non-empty tree is greater than a specified key value if
- its key is greater than the specified key, and
it is itself ordered
is_ordered( btree(K1,L,R) > K ) :- K1 > K , is_ordered( btree(K1,L,R) ) .