Rooted Binary Trees in Prolog
Full / Perfect Rooted Binary Trees in Prolog
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Full / Perfect Rooted Binary Trees in Prolog
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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 % e stands for an empty (sub-)tree
% A Rooted Binary Tree (RBT) is an empty data structure
% or a recursive data structure in which any node is
% root for at most two rooted binary trees - left and right
% sub-trees, each of them posibly being empty.
PREDICATES
lconcat(lr,lr,lr)
sublistlens(llr,lr)
lcount(lr,r)
CLAUSES
lconcat([],L,L).
lconcat([H|T],L,[H|TR]):-lconcat(T,L,TR).
sublistlens([H],[R]):-!,lcount(H,R).
sublistlens([H|T],[HL|TL]):-
lcount(H,HL),
sublistlens(T,TL).
lcount([_],1):-!.
lcount([_|T],R):-
lcount(T,Ri),
R=Ri+1.
/**************** Define root-to-leaf paths *****************/
PREDICATES
root2leaf_path(rbt,lr)
CLAUSES
root2leaf_path(t(H,e,e),[H]):-!.
root2leaf_path(t(H,L,R),[H|T]):-
root2leaf_path(L,T);
root2leaf_path(R,T).
/***********************************************/
/******** Is it FULL? *********/
% A Rooted Binary Tree is said to be FULL if and
% only if any non-leaf node posses exactly two
% siblings (out-degree of any non-leaf node is 2)
PREDICATES
isthisrbt_full(rbt)
CLAUSES
isthisrbt_full(t(_,e,e)):-!.
isthisrbt_full(t(_,L,R)):-
isthisrbt_full(L),
isthisrbt_full(R).
/***********************************************/
/******** Is it PERFECT? *********/
PREDICATES
isthisrbt_perfect(rbt)
repetition(lr)
CLAUSES
isthisrbt_perfect(t(_,e,e)):-!.
isthisrbt_perfect(T):-
isthisrbt_full(T),
findall(X,root2leaf_path(T,X),PL),
sublistlens(PL,DL), % PathList, DepthList
repetition(DL).
repetition([_]):-!.
repetition([X,X|T]):-repetition([X|T]).
/***********************************************/
]]>