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.

please give an example what you mean by "counting node with only one child" — false, Feb 01 '15 at 19:08
for example, bt(1,bt(2,nil,bt(3,nil,nil)),bt(nil))). 1 and 2 are the nodes with only one child. — bbbBB, Feb 01 '15 at 19:12

score 1 · Answer 1 · edited May 23 '17 at 12:14

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)

I got the idea, but (if_/3) causes error on every tree except for nil. I'll try to fix it. — bbbBB, Feb 01 '15 at 19:58
@bbbBB: You need to follow the link above and include the definition of `if_/3`. — false, Feb 01 '15 at 22:12

score 0 · Accepted Answer · answered Feb 01 '15 at 20:17

cbt(nil, 0).
cbt(bt(_,L,R), T) :- cbt(L,Nl),cbt(R,Nr),
    ( (L=nil,R\=nil ; L\=nil,R=nil) -> C = 1 ; C = 0 ),
    T is Nl + Nr + C.

but the test tree you give in your question seems not valid: I tested with

?- cbt(bt(1,bt(2,nil,bt(3,nil,nil)),nil),N).
N = 2.

Binary Tree counting nodes in prolog

2 Answers2