使用累加器的树的大小 [英] size of tree using accumulator

问题描述

我正在尝试学习序言，并陷入其中一个玩具示例中。 binary_tree 的定义为：

I am tryin to learn prolog and got stuck in one of the toy example. binary_tree is defined as:

术语'-'（减号）代表空树。术语
t（L，V，R）表示一棵具有左子树L，节点值V和
右子树R的树。

The term '-' (the minus symbol) represents the empty tree. The term t(L,V,R) represents a tree with left subtree L, node value V, and right subtree R.

现在我正在尝试写谓词 size（Tree，N）来查找树的大小。我知道可以使用以下命令：

now Im trying to write the predicate size(Tree,N) to find the size of tree. I know it is possible using the following :

size( -,0).
size( t(L, _,R), S) :- size(L,Ls), size(R,Rs), S is Ls + Rs + 1.

但我想使用累加器使其工作。我累了一些（和一些其他东西），但没有用：

but I want to make it work using accumulator. I tired something like(and some other stuffs) but none is working:

size(t(L,_,R),N):-size(t(L,_,R),0,N).

size(-,A,A).
size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.

例如测试用例：

size(t(-,n,t(-,m,-)),N).

我得到 5 而不是 2 。
是跟踪：

I get 5 instead of 2. here is the trace:

[debug] [7] 85 ?- trace,size(t(-,n,t(-,m,-)),N).
   Call: (73) size(t(-, n, t(-, m, -)), _G10307) ? creep
   Call: (74) size(t(-, _G10422, t(-, m, -)), 0, _G10307) ? creep
   Call: (75) _G10435 is 0+1 ? creep
   Exit: (75) 1 is 0+1 ? creep
   Call: (75) size(-, 1, _G10437) ? creep
   Exit: (75) size(-, 1, 1) ? creep
   Call: (75) size(t(-, m, -), 1, _G10437) ? creep
   Call: (76) _G10438 is 1+1 ? creep
   Exit: (76) 2 is 1+1 ? creep
   Call: (76) size(-, 2, _G10440) ? creep
   Exit: (76) size(-, 2, 2) ? creep
   Call: (76) size(-, 2, _G10440) ? creep
   Exit: (76) size(-, 2, 2) ? creep
   Call: (76) _G10441 is 2+2 ? creep
   Exit: (76) 4 is 2+2 ? creep
   Exit: (75) size(t(-, m, -), 1, 4) ? creep
   Call: (75) _G10307 is 1+4 ? creep
   Exit: (75) 5 is 1+4 ? creep
   Exit: (74) size(t(-, _G10422, t(-, m, -)), 0, 5) ? creep
   Exit: (73) size(t(-, n, t(-, m, -)), 5) ? creep
N = 5.

我觉得我需要两个不同的累加器，但不确定怎么做。我将不胜感激，因为我正在尝试学习这些东西。

I feel I need to have two different accumulator but not sure how do that.I would appreciate any explanation (rather than straight answer) since I am trying to learn this stuff.

推荐答案

您在计算子树两次：

size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.
                                      ^^            ^^      ^^^^^^^^

值 A1 已使用两次。您真正想要的是描述一个差异（不是差异列表，而是一个非常相似的东西）。

The value A1 is used twice. What you actually want is to describe a difference (not a difference list but something very similar).

size(-, N,N).            % N-N   ... 0
size(t(L,_,R), N0,N) :-  % N-N0  ... the total size
   N1 is N0+1,           % N1-N0 ... 1
   size(L, N1,N2),       % N2-N1 ... size of L
   size(R, N2,N).        % N-N2  ... size of R

请为变量标记模式。第一个是 N0 ，最后一个是 N 。它们几乎类似鞋带的地方散布。

Please remark the pattern for the variables. The first is N0 and the last is N. They are spread almost shoelace-like.

这篇关于使用累加器的树的大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！