在PROLOG中查找二叉树中的元素

Question

我正在尝试使用Prolog实现它以在二叉树中查找元素。

elem1(tree(Element,void,void),Element).

elem1(tree(_Element,Left,Right),N) :-
  elem1(Left,N), 
  elem1(Right,N).

因为我认为< code>elem1检查我的树的根是否是我搜索的一个元素，并且它处理这个输出。

?- trace,elem1(tree(c,void,void),c).
Call: (9) elem1(tree(c, void, void), c) ? creep
Exit: (9) elem1(tree(c, void, void), c) ? creep
true

但是以这样的递归方式：

  ?- trace,elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).
  Call: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) 
  creep
  Call: (10) elem1(tree(1, void, void), 1) ? creep
  Exit: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (10) elem1(tree(2, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(2, void, void), 1) ? creep
  Redo: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(1, void, void), 1) ? creep
  Fail: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) ? 
  creep

  false.

似乎调用正确的方式（10）并检查正确的谓词，但之后尝试扩展更多并给我一个失败。

我不知道为什么会发生这种情况，但基本情况很好，所以我认为当找到一个元素时，退出并给出true，因为基本谓词是有效的。

Answer 1

您的代码稍加html" target="_blank">修改，以显示和(，)的用法。

elem_01(tree(Element,void,void),Element).

elem_01(tree(_Element,Left,Right),N) :-
  (
    elem_01(Left,N)
  ,
    elem_01(Right,N)
  ).

例子：

?- elem_01(tree(4,tree(1,void,void),tree(2,void,void)),1).
false.

这给出了不正确的结果。

使用或(；).

elem_02(tree(Element,void,void),Element).

elem_02(tree(_Element,Left,Right),N) :-
  (
    elem_02(Left,N)
  ;
    elem_02(Right,N)
  ).

例子：

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

在二叉树中正确查找< code>1。

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

正确显示3不在树中。

已更正版本，显示使用了两个子句，而不是OR(；).

elem_03(tree(Element,void,void),Element).

elem_03(tree(_Element,Left,_),N) :-
    elem_02(Left,N).

elem_03(tree(_Element,_,Right),N) :-
    elem_02(Right,N).

例子：

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

在二叉树中正确查找< code>1。

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

正确显示3不在树中。

在你的问题中，你把树显示为

elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).

e. g. g.

  4
 / \
1   2

虽然它是一个二叉树，但它不是一个正确的二叉树，其中左边的键小于根，右边的键大于根。

您需要按此方式键入键的原因是，您可以在搜索时使用比较，这样就不必搜索整个树。

您的代码可以工作，但是如果缺少值，它必须搜索整个树。如果您有一棵非常大的树并且没有匹配，那么如果您正确构建树并将比较添加到代码中，您可以更快地发现它丢失了。

这是一个适合您的示例的树：

elem1(tree(2,tree(1,void,void),tree(4,void,void)),1).

e. g. g.

  2
 / \
1   4