在prolog中打印出preOrder遍历

Question

我正在prolog中实现一个二进制搜索树，并试图为每种遍历类型( preOrder、inOrder和postOrder )提供打印。

我的测试树是：bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty)).

到目前为止，我的情况如下：

preOrder(bst(_,X,_)) :- write(X).
preOrder(bst(L,_,_)) :- preOrder(L).
preOrder(bst(_,_,R)) :- preOrder(R).

它可以工作，但用户必须按下空间才能得到每个元素。

5
True
4
True
2
True
8
True
6
False

我宁愿用5 4 2 8 6表格打印出来

因此，我将上面的代码修改为：

preOrder(bst(L,X,R)) :- write(X), write(" "), preOrder(L), preOrder(R).

现在它只打印出5 4 2 false

我对prolog非常陌生，有人能解释为什么将单个谓词添加到一个谓词中与3个单独谓词的作用不同吗？

Answer 1

为什么将单个谓词添加到一个谓词中与3个单独谓词的操作不同？

带有多个子句的谓词(称为单个谓词)被计算为OR，带有多个由,分隔的语句的单个子句谓词被计算为AND。

如果你改变这个

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    preOrder_04(L),
    preOrder_04(R).

它也可以写成

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ,
        preOrder_04(R)
    ).

至

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ;
        preOrder_04(R)
    ).

那你就会得到你想要的。

由于您是Prolog的新手，所以我也将对您的代码进行回顾。

使用原始树和谓词

bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty))

preOrder(bst(_,X,_)) :- write(X).
preOrder(bst(L,_,_)) :- preOrder(L).
preOrder(bst(_,_,R)) :- preOrder(R).

是我干的

tree(bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty))).

test_01 :-
    tree(T),
    preOrder_01(T).

preOrder_01(bst(_,X,_)) :- write(X).
preOrder_01(bst(L,_,_)) :- preOrder_01(L).
preOrder_01(bst(_,_,R)) :- preOrder_01(R).

tree(T)行将树作为事实读取，然后将树绑定到变量T，这样我就不必每次输入它。

然后，我创建了一个名为_01的测试谓词，这样就不会与即将到来的其他测试发生冲突。

示例运行：

?- test_01.
5
true ;
4
true ;
2
true ;
8
true ;
6
true ;
false.

为什么每次回答后你都要按空格键？

(这是使用完成的)。

这个例子说明了原因。

test_02 :- write("First").
test_02 :- write("Second").

?- test_02.
First
true ;
Second
true.

每次执行谓词test_02/0时，它都会产生一个解决方案，当给出一个解决方案时，您必须按空格键才能看到下一个解决方案。

还请注意第一个答案末尾的;。这是Prolog告诉您，存在一个选择点，并且可能会有另一个答案。如果它是一个.，那么就没有更多的答案了。

因为你的重写不起作用

preOrder_03(bst(L,X,R)) :-
    write(X),
    write(" "),
    preOrder_03(L),
    preOrder_03(R).

test_03 :-
    tree(T),
    preOrder_03(T).

示例运行：

?-  test_03.
5 4 2 
false.

如果您使用跟踪运行它，您将看到它没有到达选择点。

请参阅What is redo in Prolog when you trace?

但是如果你这样做

preOrder_04(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ;
        preOrder_04(R)
    ).

test_04 :-
    tree(T),
    preOrder_04(T).

示例运行：

?- test_04.
5 4 2 8 6 
false.

你会得到你想要的。preOrder_03和preOrder_04的主要区别在于，preOrder_03在一个地方有一个,，而preOrder_04在一个地方有一个;。逗号(,)是逻辑AND，分号(;)是逻辑OR。