CODEWITHSUNDEEP
prologdcg
Mark
Mark

Reputation: 1769

Tree path in a List of Lists

I want to build a predicate (Prolog) that takes a tree and returns a list of lists and each list is a tree path. The tree is defined as tree(Root,LeftTree,RightTree). Do you have any suggestions, please?

Upvotes: 1

Views: 504

Answers (1)

mat
mat

Reputation: 40768

This is quite unusual (it is more common to ask for example for a relation between a tree and a flat list of all its nodes, for which DCGs are a good fit), maybe like this:

tree_list(nil, []).
tree_list(tree(Node,Left,Right), [Lefts,Node,Rights]) :-
        tree_list(Left, Lefts),
        tree_list(Right, Rights).

Example:

?- tree_list(tree(a,tree(b,nil,tree(d,nil,nil)),tree(c,nil,nil)), Ts).
Ts = [[[], b, [[], d, []]], a, [[], c, []]].

This representation is wasteful (you know that all non-empty lists will have 3 elements, so why not use a ternary term instead of a list?) and in my opinion unnecessary (because you already have the tree representation in the first place), but who knows what it is good for...

Upvotes: 4

Related Questions