Trying to print out preOrder Traversal in prolog

Question

I'm implementing a Binary Search Tree in prolog and I'm trying to have printouts for each traversal type, preOrder, inOrder, and postOrder.

My test Tree is: bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty)).

Here's what I have so far:

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

And it works but the user has to press space to get each element.

5
True
4
True
2
True
8
True
6
False

I'd rather it print out in the form 5 4 2 8 6

So I modified the code above to:

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

Now it only prints out 5 4 2 false

I'm pretty new to prolog, can anyone explain why adding the individual predicates to one single predicate is acting differently than 3 separate ones?

It's best to use [tag:dcg] for traversals – false Dec 15 '18 at 17:09 — false, Dec 15 '18 at 17:09

score 1 · Accepted Answer · answered Dec 15 '18 at 18:39

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

A predicate with multiple clauses (what you call individual predicates) are evaluated as OR, and a single clause predicate with multiple statements separated by , is evaluated as AND.

If you change this

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

which can also be written as

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

to

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

then you will get what you seek.

Since you are new to Prolog I will also give you a review of your code.

To use your original tree and predicates

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

I did this

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

the line tree(T) read the tree as a fact and then bound the tree to the variable T so I would not have to type it in each time.

Then I created a test predicate with the name _01 so I would not clash with other test to come.

Example run:

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

Why do you have to press the space bar after each answer?

(This was done using SWI-Prolog).

This example shows why.

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

?- test_02.
First
true ;
Second
true.

Each time the predicate test_02/0 is executed it results in a solution and when a solution is given you have to press the space bar to see the next solution.

Also notice the ; at the end of the first answer. This is Prolog telling you that a choice point exists and there may be another answer. If it were a . then there would be no more answers.

For your rewrite which doesn't work

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

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

Example run:

?-  test_03.
5 4 2 
false.

If you run it with the trace you will see that it doesn't reach a choice point.
See What is redo in Prolog when you trace?

However if you do this

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

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

Example run:

?- test_04.
5 4 2 8 6 
false.

You will get what you seek. The key difference between preOrder_03 and preOrder_04 is that preOrder_03 has a , at one place and preOrder_04 has a ; at one place. A comma (,) is a logical AND and a semicolon (;) is a logical OR.

Thank you so much! You helped tremendously, really appreciate the links to other resources and extra tips for writing code in the future! — Jambo, Dec 15 '18 at 21:09

Trying to print out preOrder Traversal in prolog

1 Answers1