prolog traverse nonstandard tree left to right

Question

I need to implement a predicate trav(Tree,List) that performs a left to right tree traversal;

Where: Tree is defined by the structure node(left,right), where left and right can be either another node or any Prolog data item. List is the list of leaf node values in the tree.

For example:

?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .

What I have so far:

trav(tree,[ ]).
trav(node(Left,Rigth), L) :-
    trav(Left, L),
    trav(Right, L),
    append(Left,[Left|Right],L).

You have again a problem with what you want a tree to be! Define first a predicate is_tree/1 that states what a tree is in you opinion. It is very uncommon, but certainly possible to have nodes without elements. Such nodes typically occur for expression-trees. But otherwise they do not occur. — false

Matt Matt · Accepted Answer · 2015-06-07T03:11:36

My Prolog is slightly rusty, but I believe that this should do it:

node(Left, Right).

trav(node(Left, Right), L) :- 
  trav(Left, L1), 
  trav(Right, L2),
  append(L1, L2, L).
trav(X, [X]) :- X \= node(A, B).

Intuitively, trav(Left, L1) says traverse the left subtree, storing each element in L1. trav(Right, L2) says traverse the right subtree storing each element in L2. Lastly, append(L1, L2, L) append the two lists, L1 and L2 into list L. For a leaf, trav(X, [X]), puts X into a singleton list as long as it does not unify with a node.

prolog traverse nonstandard tree left to right

1 Answers