Tree postorder traversal in Prolog

问题:

Tree traversal refers to the process of visiting each node in a tree data structure in a systematic way. The postorder traversal in the following image

Sorted_binary_tree

returns A, C, E, D, B, H, I, G, F (left, right, root). The Prolog code for PREORDER traversal is

preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls),
    preorder(R,Rs),
    append([X|Ls],Rs,Xs).

preorder(void,[]).

I would like to modify the above code to implement postorder traversal.

回答1:

In case of a postorder you have to traverse the left branch and get a list of node values Left, then traverse the right branch and get a list of node values Right, and finally return the concatenation of Left, Right and the node value.

Therefore, to modify your code would be to rearrange the way in which you instantiate the resulting list:

postorder(tree(X, L, R), Xs):-
  postorder(L, Ls),
  postorder(R, Rs),
  append(Ls, Rs, Xs1),
  append(Xs1, [X], Xs).
postorder(void, []).

Note however, that this code is suboptimal in the sense that it is not tail recursive. You should consider implementing it with the aid of an accumulator.

回答2:

Folks, please consider using DCGs when describing lists, for example:

preorder(void) --> [].
preorder(tree(X, L, R)) -->
        [X],
        preorder(L),
        preorder(R).

Usage:

?- phrase(preorder(Tree), List).

You get different orders by simply deciding where to place the [X] in the sequence.