CODEWITHSUNDEEP
prologdcgmultiway-treepostorder
user3002495
user3002495

Reputation: 11

PROLOG (How to postorder a multiway tree )

I'm struggling with a Prolog homework like below,

Prolog uses general trees, not binary trees. An example is 

     a(b,c,d(e,f,g))   where root a has 3 kids, as does kid d.

 It is possible to define both preorder and postorder for general trees, 
 although inorder of course makes no sense.

 For this assignment we are interested in postorder, which is defined as
 follows:

   to 'visit' a tree in postorder, 
      you visit the subtrees of the root, in left to right order,
      in postorder, and then you visit the root

 Thus the example above would yield the following postorder traversal:

        b c e f g d a

  Write Prolog code which will perform a postorder traversal of a Prolog
 tree constant.   Hint: you might use 'univ', or its cousins.

 Sample dialog:

 ?- postorder(a(b,c,d(e,f,g))).
 b c e f g d a    true

Any help of this puzzle is appreciated.

Upvotes: 1

Views: 1377

Answers (3)

Harsh Shah
Harsh Shah

Reputation: 418

postorder([]).
postorder(Tree):- Tree =..[Parent|Children] , myfun(Children), write(Parent),write(' ').
myfun([First|Next]):- atom(First), write(First), write(' '), myfun(Next).
myfun([First|Next]):- postorder(First),myfun(Next).
myfun([]).

Upvotes: 0

mat
mat

Reputation: 40768

I give you a solution that works for a cleaner data representation, which works solely by pattern matching and does not require any univ etc. I uniformly present all trees in the form tree(Node, Children). Your example can be written in this representation as:

example(T) :-
        T = tree(a, [tree(b,[]),
                     tree(c,[]),
                     tree(d, [tree(e,[]),
                              tree(f,[]),
                              tree(g,[])])]).

Now, as you are describing a list of nodes, consider using a DCG. For example:

postorder(tree(Node, Children)) -->
        postorder_(Children),
        [Node].

postorder_([]) --> [].
postorder_([C|Cs]) -->
        postorder(C),
        postorder_(Cs).

Example query with the above definitions and its result:

?- example(T), phrase(postorder(T), Ns).
T = tree(a, ...),
Ns = [b, c, e, f, g, d, a].

I leave it as a simple exercise to make this DCG work with your representation of trees (which I do not recommend, since you cannot describe solutions via pattern matching alone although that is clearly possible with a different representation, as I show above).

Upvotes: 3

Shevliaskovic
Shevliaskovic

Reputation: 1564

tree :-
Tree= [1,
        [2,
       [4,
         [7, nil, nil],
         nil], 
       [5, nil, nil]],
        [3,
     [6,
       [8, nil, nil], 
       [9,nil, nil]], 
     nil]],

write('preorder    : '), preorder(Tree), nl,
write('inorder     : '), inorder(Tree), nl,
write('postorder   : '), postorder(Tree), nl,
write('level-order : '), level_order([Tree]),!.

preorder(nil).
preorder([Node, FG, FD]) :-
format('~w ', [Node]),
preorder(FG),
preorder(FD).


inorder(nil).
inorder([Node, FG, FD]) :-
inorder(FG),
format('~w ', [Node]),
inorder(FD).

postorder(nil).
postorder([Node, FG, FD]) :-
postorder(FG),
postorder(FD),
format('~w ', [Node]).


level_order([]).

level_order(A) :-
level_order_(A, U-U, S),
level_order(S).

level_order_([], S-[],S).

level_order_([[Node, FG, FD] | T], CS, FS) :-
format('~w ', [Node]),
append_dl(CS, [FG, FD|U]-U, CS1),
level_order_(T, CS1, FS).

level_order_([nil | T], CS, FS) :-
level_order_(T, CS, FS).


append_dl(X-Y, Y-Z, X-Z).

via Rosetta Code - Tree Traversal in Prolog

The code has preorder, inorder, postorder and level order.

Take a look at them all, you might find them useful.

Output:

?- tree.
 preorder    : 1 2 4 7 5 3 6 8 9 
 inorder     : 7 4 2 5 1 8 6 9 3 
 postorder   : 7 4 5 2 8 9 6 3 1 
 level-order : 1 2 3 4 5 6 7 8 9 
true .

Edit: At the end of the tree query I added the ! so it will stop the backtracking on the first true.. Otherwise after true., if you typed ; you would get true. again and again and again.

Upvotes: 0

Related Questions