序言递归返回多个结果

开始这是一个准备给我的作业问题。序言递归返回多个结果

我应该写一个谓词btree_height \ 2，它需要一棵二叉树并且（现在）只返回树的高度。

二进制树被表示为：

node(node(leaf, x, leaf), x, node(leaf, x, leaf))

其中x是节点的整数值。（这只是一个示例树）。

我的代码如下：

btree_height(leaf, 0). 
btree_height(node(leaf,_,leaf), 1). 
btree_height(node(LT,_,RT), D):- 
    btree_height(LT, DL), 
    btree_height(RT, DR), 
    D is max(DL,DR)+1.

，我遇到的问题是，当我打电话btree_height（BT，d），并用一个BT供给它，如果深度为4则递归4次并将数字4“返回”四次。据我的教授说，这是一个不正确的行为，因为它应该只返回一次数字4。（使用上面的例子，它返回数字2两次）

这是我第一次在Prolog中编码，我不知道应该从哪里开始寻找。

这在技术上是SWI-Prolog的，如果它有差别......

来源

2012-10-12 OmegaTwig

注我删除'homework'标记[因为它已被正式弃用]（http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated） – kaveman

由于这是家庭作业，我不会给你完整的解决方案。

当您的谓词击中匹配node(leaf, _, leaf)的节点时，它首先执行第二个子句。那会返回一个。然后，当您要求它回溯时，它也会执行第三个条款，因为也匹配LT=leaf和RT=leaf的输入，所以它会递归两次并且两次都击中leaf的情况。

下一次，如果你要调试这样的问题自己，trace/1是一个很好的工具：（它说creep，我按输入）

2 ?- trace. 
true. 

[trace] 2 ?- btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), H). 
    Call: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), _G821) ? creep 
    Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) _G821 is max(1, 1)+1 ? creep 
    Exit: (7) 2 is max(1, 1)+1 ? creep 
    Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep 
H = 2 ; 
    Redo: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Call: (8) btree_height(leaf, _G903) ? creep 
    Exit: (8) btree_height(leaf, 0) ? creep 
    Call: (8) btree_height(leaf, _G903) ? creep 
    Exit: (8) btree_height(leaf, 0) ? creep 
    Call: (8) _G911 is max(0, 0)+1 ? creep 
    Exit: (8) 1 is max(0, 0)+1 ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) _G821 is max(1, 1)+1 ? creep 
    Exit: (7) 2 is max(1, 1)+1 ? creep 
    Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep 
H = 2

来源

2012-10-12 23:52:33

谢谢！我刚刚结束删除btree_height（node（leaf，_，leaf），1）行，因为我已经有一个基本情况。现在我觉得很愚蠢...... – OmegaTwig

序言递归返回多个结果

回答

相关问题