Binary Tree counting nodes in prolog

3
votes

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.

2
prolog
please give an example what you mean by "counting node with only one child" – false
for example, bt(1,bt(2,nil,bt(3,nil,nil)),bt(nil))). 1 and 2 are the nodes with only one child. – bbbBB

2 Answers

1
votes

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)

0
votes
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.