How to count the leaves of a tree in prolog?

user_13137621 0
Viewed 165

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.

prolog tree
3 Answers

So a leaf is a node pointing to 2 nils, right?

nleaves(nil,0).
nleaves(node(_,nil,nil),1).
nleaves(node(_,Left,Right),N):- 
    dif((Left,Right), (nil,nil)),
    nleaves(Left,N1),
    nleaves(Right,N2),
    N is N1+N2.
user_80806480

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.

user_675790

This is a strange definition of a tree; the more normal definition has a type that looks like this:

leaf(Value)
node(Left, Right)

Then you can traverse it like this (I'm using DCG notation -- if you don't understand what's going on, do the query listing(preorder) to see the code expansion):

preorder(leaf(Value)) --> [Value].
preorder(node(Left, Right)) -->
    preorder(Left),
    preorder(Right).

%           *
%         /  \
%       1
%           /  \
%               4
%         / \
%        2   3

test(Values) :-
    phrase(preorder(
                    node(leaf(1),
                         node(node(leaf(2), leaf(3)),
                              leaf(4)))),
           Values).

?- test(V).
V = [1, 2, 3, 4].

If you want to know how many leaves, just use the length/2 predicate on Values. Or you can modify the accumulator to do the arithmetic:

count_leaves(Tree, Count) :-
    count_leaves(Tree, 0, Count).

count_leaves(leaf(_), Count0, Count) :-
    Count is Count0 + 1.
count_leaves(node(Left, Right), Count0, Count) :-
    count_leaves(Left, Count0, Count1),
    count_leaves(Right, Count1, Count).
user_91434020
Related