Rooted Binary Trees in Prolog
Tree Sort
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Trees in Prolog: Tree Sort
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Trees (RBT)
CONSTANTS
t1 = t(4,t(3,t(8,t(1,e,e),e),t(0,t(2,e,e),t(2,e,t(3,e,t(5,e,e))))),t(5,e,t(1,t(4,e,e),t(3,t(5,e,e),t(2,e,e))))) % a tree for running the tests.
% t1 is not FULL:
% ________4________
% ____3____ 5______
% __8 __0__ ____1____
% 1 2 2__ 4 __3__
% 3__ 5 2
% 5
%
l1=[4,3,5,8,0,1,1,2,2,4,3,3,5,2,5]
l2=[9,8,7,6,5,4,3,2,1,0,9,8,7,6,5,4,3,2,1,0]
l3=[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2]
l4=[9,5,6,2,1,4,3,5,4,7,6,2,4,8,7,3,6,0,6,2] %rnd
l5=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
l6=[0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9]
l7=[1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8]
l8=[0,9,1,8,2,7,3,6,4,5,5,4,6,3,7,2,8,1,9,0]
% 40 rnd elements:
l9=[5,8,2,9,3,0,6,9,3,5,2,7,4,9,6,1,4,2,7,5,4,8,2,7,2,8,1,6,3,8,4,0,5,7,2,8,4,8,5,1]
t2 = t( 4, t(3,t(8,t(1,e,e),t(4,e,e)),t(0,t(2,e,e),t(2,t(1,e,e),t(3,t(8,e,e),t(5,e,e))))), t(5,t(2,e,e),t(1,t(4,e,e),t(3,t(5,e,e),t(2,e,e)))) )
% t2 is FULL but not PERFECT:
% _________4_________
% _____3_____ ____5______
% __8__ ___0___ 2 ____1____
% 1 4 2 __2__ 4 __3__
% 1 __3__ 5 2
% 8 5
%
t3 = t( 4, t(3,t(8,t(1,e,e),t(4,e,e)),t(0,t(2,e,e),t(2,e,e))), t(5,t(2,t(0,e,e),t(8,e,e)),t(1,t(4,e,e),t(3,e,e))) )
% t3 is PERFECT (hence, it is also FULL):
% _________4_________
% _____3_____ _____5_____
% __8__ __0__ __2__ __1__
% 1 4 2 2 0 8 4 3
DOMAINS
r=real
lr=r*
llr=lr*
rbt = t(r,rbt,rbt);e
PREDICATES
lconcat(lr,lr,lr)
CLAUSES
lconcat([],L,L).
lconcat([H|T],L,[H|TR]):-lconcat(T,L,TR).
/******** INORDER traversal of a tree ***/
% inoder/infix/symetric/srd/lRr traversal
PREDICATES
inorder(rbt,lr)
CLAUSES
inorder(e,[]):-!.
inorder(t(X,L,R),TL):-
inorder(L,LL),
inorder(R,RL),
lconcat(LL,[X|RL],TL).
/***********************************************/
/******** Convert a List to a Binary Search Tree *********/
PREDICATES
list2binary_search_tree(lr,rbt)
ins2binary_search_tree(lr,rbt,rbt)
CLAUSES
list2binary_search_tree([],e):-!.
list2binary_search_tree([X],t(X,e,e)):-!.
list2binary_search_tree([H|T],B):-ins2binary_search_tree(T,t(H,e,e),B).
ins2binary_search_tree([],B,B):-!.
ins2binary_search_tree([H],e,t(H,e,e)):-!.
ins2binary_search_tree([H],t(X,L,R),t(X,HL,R)):-
H<=X,!,ins2binary_search_tree([H],L,HL).
ins2binary_search_tree([H],t(X,L,R),t(X,L,HR)):-
H>X, !,ins2binary_search_tree([H],R,HR).
ins2binary_search_tree([H|T],Ri,B):-
ins2binary_search_tree([H],Ri,Ria),
ins2binary_search_tree(T,Ria,B).
/***********************************************/
/**************** Tree Sort *****************/
PREDICATES
tree_sort(lr,lr)
min(lr,r)
max(lr,r)
last(lr,r)
CLAUSES
tree_sort(L,SL):-
list2binary_search_tree(L,BST),
inorder(BST,SL).
min(L,R):-tree_sort(L,[R|_]).
max(L,R):-tree_sort(L,SL),last(SL,R).
last([H],H):-!.
last([_|T],R):-last(T,R).
/***********************************************/
]]>