Prolog Postorder Traversal in a general tree using univ

Question

I am trying to traverse a general tree in prolog in a postorder way. I found a lot of binary tree postorder traversals but could not use them to my purpose. I wrote a program but it only prints my tree in the reverse way of how it is entered, ie for input

?-postorder(a(b,c,d(e,f,g))).
->g f e d c b a true (is what I get)
->b c e f g d a true (what i want to get)

Here is the code i have managed to write till now

postorder([]).
postorder(List):- List =..X , myfun(X).
myfun([A|B]):- atom(A), myfun(B),write(A),write(' ').
myfun([A|B]):- postorder(A),myfun(B).
myfun([]).

I am not getting a way for postorder traversal
Any help is much appreciated

Answer 1

Here is the solution that works just fine for me.

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([]).

Answer 2

your naming of arguments it's a bit confusing

postorder(List):- List =..X , myfun(X).

should read

postorder(Struct):- Struct =.. List, myfun(List).

Now should be clearer that you must write the structure functor there:

postorder(Struct):-
  Struct =.. [Functor|Arguments], myfun(Arguments), write(Functor).

At this point, you should change myfun as well...

As an example, here is a compact solution of the problem

postorder(X) :- X =.. [H|As], maplist(postorder, As), write(H).

that yields

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

Answer 3

An alternative way of doing it-

Suggestion - I would structure your tree a little differently, specifically, a tree is in the form

tree(Value,[Subtrees])

where value would be something like a and then the list is a list of subtrees. A leaf has the empty list []

If doing that, you can use this algorithm utilizing unification-

postorder(tree(VAL,[Child1|ChildList])) :- postorder(Child1),postorder(tree(VAL,ChildList)).
postorder(tree(VAL,[])) :- write(VAL).

output:

?- postorder(tree(a,[tree(b,[]),tree(c,[]),tree(d,[tree(e,[]),tree(f,[]),tree(g,[])])])).
bcefgda
true .