尝试在 prolog 中打印出 preOrder Traversal

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).

它可以工作，但用户必须按 space 才能获取每个元素。

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

Why adding the individual predicates to one single predicate is acting differently than 3 separate ones?

具有多个子句的谓词（您所说的单个谓词）被计算为 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.

为什么每次回答后都必须按 space 栏？

（这是使用 SWI-Prolog 完成的）。

这个例子说明了原因。

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

?- test_02.
First
true ;
Second
true.

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

另请注意第一个答案末尾的 ;。这是 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.

如果你运行它与跟踪你会看到它没有到达选择点。
参见

但是如果你这样做

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.

尝试在 prolog 中打印出 preOrder Traversal

Trying to print out preOrder Traversal in prolog

prolog

binary-search-tree

preorder