Rooted Binary Trees in Prolog
Counting leaves and nodes
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Trees in Prolog: counting leaves and nodes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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).
/******** Counting the nodes of a Rooted Binary Tree *******/
PREDICATES
rbt_count_nodes(rbt,r)
CLAUSES
% Count the nodes of a RTB, including the leaves:
rbt_count_nodes(e,0):-!.
rbt_count_nodes(t(_,L,R),N):-
rbt_count_nodes(L,NL),
rbt_count_nodes(R,NR),
N=NL+NR+1.
% USAGE:
% rbt_count_nodes(t1,X)
/***********************************************/
/******** Counting the leaves of a Rooted Binary Tree ******/
PREDICATES
rbt_count_leaves(rbt,r)
CLAUSES
% Count the leaves of a RTB:
rbt_count_leaves(e,0):-!.
rbt_count_leaves(t(_,e,e),1):-!.
rbt_count_leaves(t(_,L,R),N):-
rbt_count_leaves(L,NL),
rbt_count_leaves(R,NR),
N=NL+NR.
% USAGE:
% rbt_count_leaves(t1,X)
/***********************************************/
/******** Counting non-terminal nodes of a Rooted Binary Tree ******/
PREDICATES
rbt_count_ntnodes(rbt,r)
CLAUSES
% Count non-terimnal nodes of a RTB:
rbt_count_ntnodes(e,0):-!.
rbt_count_ntnodes(t(_,e,e),0):-!.
rbt_count_ntnodes(t(_,L,R),N):-
rbt_count_ntnodes(L,NL),
rbt_count_ntnodes(R,NR),
N=NL+NR+1.
% USAGE:
% rbt_count_ntnodes(t1,X)
/***********************************************/
]]>