tree - 如何计算序言中树的叶子？

Question

我正在尝试计算树叶的总和，但似乎无法正确完成任何帮助，我们将不胜感激。我尝试了几种不同的方法，但似乎没有一种能正常工作。

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

当我询问查询 ?- nleaves(3, node(1, node(2, node(3, nil, nil), node(4, nil, nil)), node(5,nil, nil)), N)., 它返回N = 0。现在，如果我在基本情况下将 0 替换为 1 并提出相同的查询，它会返回 N = 6。然后，如果我完全操纵完全错误且 Not Acceptable 谓词

nleaves(nil, 0).
nleaves(node(_, Left, Right), N) :- 
    nleaves(Left, LN), 
    nleaves(Right, RN),
    N is 3 - LN + RN.

然后它会输出 N = 3。

我该怎么做才能让它以正确的方式说 N = 3？我数不清树叶了。我似乎能够使用 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.

但我不知道如何数叶子。

Answer 1

所以叶子是指向 2 个 nils 的节点，对吗？

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.