序言需要计算树的大小(prolog need to compute the tree size)

我需要用树的大小： size(Tree,Size)

我至今是错误的，请指教！

size(empty, Size).
size(tree(L, _, R), Size) :-
    size(L, Left_Size),
    size(R, Right_Size),
    Size is
        Left_Size + Right_Size + 1.

输出应该产生：

?- size(node(1,2),X).
X = 2.
?- size(node(1,[2,3,4]),X).
X = 2.
?- size(node(node(a,b),[2,3,4]),X).
X = 3.

Answer 1:

Prolog是一个说明性语言，你必须正确地说出你的模式：

size(node(L,R), Size) :- ... % why you add 1 to left+right sizes ?

从样品，我建议停止与尺寸的递归= 1时，任何不是一个节点看出：

size(node(L,R), Size) :- !, ...
size(_, 1).

Answer 2:

size_tree（零，0）。 ％零模拟空节点

size_tree（节点（根，左，右），尺寸）： -

 Root\= nil,
 RootSize = 1,
 size_tree(Left, LeftSide),
 size_tree(Right, RightSide),
 Size is (RootSize + LeftSide + RightSide).

文章来源: prolog need to compute the tree size