I am trying to sum the leaves of a tree and cannot seem to do it correctly any help would be greatly appreciated. I have tried several different methods and none seem to work right.
nleaves(nil, 0).
nleaves(node(_,Left,Right), N) :-
nleaves(Left, N1),
nleaves(Right, N2),
N is N1 + N2.
when I ask the query ?- nleaves(3, node(1, node(2, node(3, nil, nil), node(4, nil, nil)), node(5,nil,nil)), N)., it comes back with
N = 0. Now, if I replace 0 with 1 in the base case and ask the same query, it returns N = 6. Then if I completely manipulate the predicate which is completely wrong and not acceptable
nleaves(nil, 0).
nleaves(node(_, Left, Right), N) :-
nleaves(Left, LN),
nleaves(Right, RN),
N is 3 - LN + RN.
It will then spit out N = 3.
What can I do to this to make it say N = 3 the right way? I am at a loss for counting the leaves. I seem to be able to count the height correctly with a max predicate helper.
height(nil, 0). % base case empty tree height is 0.
height(node(_,Left,Right), N) :-
height(Left, LN),
height(Right, RN),
N is max(LN, RN) + 1.
but I cannot figure out how to count the leaves.
The base predicate should be one for a leaf, and 0 for a nil, so:
nleaves(nil, 0).
nleaves(node(_, nil, nil), 1).
nleaves(node(_, Left, Right), N) :-
(dif(Left, nil); dif(Right, nil)),
nleaves(Left, L),
nleaves(Right, R),
N is L + R.Here the second clause thus counts a leaf node(_, nil, nil) as one, and a node where at least one of the two items is not nil as the sum of the leaves of the two nodes.