Binary Tree counting nodes in prolog

Question

I built the binary tree that has the stucture bt(Data,LeftTree,RightTree).

btree(nil).
btree(bt(_,L,R)) :- btree(L), btree(R).

then I want to define predicate count1Child(Tree, Count) that assert that Count is the number of nodes in the tree that have one child. I know how to count the total number of the nodes in the tree. But no idea with counting node with only one child.

Answer 1

Before you start to write a predicate, let's try to define a predicate that gives true for the nodes you want to count and false for those nodes that still may occur but that do not count. By that we implicitly also define what we want. I assume that you want only nodes that have two subtrees.

singlechild_t(nil, false).
singlechild_t(bt(_,nil,bt(_,_,_)), true).
singlechild_t(bt(_,bt(_,_,_),nil), true).
singlechild_t(bt(_,nil,nil), false).
singlechild_t(bt(_,bt(_,_,_),bt(_,_,_)), false).


tree_count(P_2, T, N) :-
   tree_count(P_2, T, 0,N).

tree_count(_, nil, N,N).
tree_count(P_2, T, N0,N) :-
   T = bt(_,L,R),
   if_(call(P_2, T), A = 1, A = 0),
   N1 is N0+A,
   tree_count(P_2, L, N1,N2),
   tree_count(P_2, R, N2,N).

 tree_countsingles(T, N) :-
    tree_count(singlechild_t, T, N).

(using if_/3)