Rooted Binary Trees in Prolog
Tree Traversals: Preorder, Inorder, Postorder
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Tree Traversals: Preorder, Inorder, Postorder
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CONSTANTS
% a Rooted Binary Tree for running the tests:
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)))))
% t1:
% ________4________
% ____3____ 5______
% __8 __0__ ____1____
% 1 2 2__ 4 __3__
% 3__ 5 2
% 5
DOMAINS
r=real
lr=r*
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 possibly being empty.
PREDICATES
lconcat(lr,lr,lr)
CLAUSES
lconcat([],L,L).
lconcat([H|T],L,[H|TR]):-lconcat(T,L,TR).
/******** PREORDER traversal (reading) of a tree ***/
% preorder/prefix/depth-first/Rlr/rsd traversal
PREDICATES
preorder(rbt,lr)
CLAUSES
preorder(e,[]):-!.
preorder(t(X,L,R),TL):-
preorder(L,LL),
preorder(R,RL),
lconcat([X|LL],RL,TL).
% preorder(e,[]):-!.
% preorder(t(X,L,R),[X|H]):-
% preorder(L,LL),
% preorder(R,RL),
% preorder(LL,RL,H).
% USAGE:
% preorder(t1,X)
/***********************************************/
/******** INORDER traversal (reading) 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).
% USAGE:
% inorder(t1,X)
/***********************************************/
/******** POSTORDER traversal (reading) of a tree ********/
% postorder / postfix / breadth-first / lrR / sdr traversal
PREDICATES
postorder(rbt,lr)
CLAUSES
postorder(e,[]):-!.
postorder(t(X,L,R),TL):-
postorder(L,LL),
postorder(R,RL),
lconcat(RL,[X],RL2),
lconcat(LL,RL2,TL).
% USAGE:
% postorder(t1,X)
/***********************************************/
]]>