Prolog get elements in different lists with BFS

i'm new at prolog and to improve my skills i'm trying to make some exercise. At the moment I'm stuck with a BFS, let assume the tree is something like this:

[tree(tree(tree(nil,b,nil),a,tree(tree(nil,d,nil),c,tree(nil,e,nil)))]

after my query i've something like

X=a;

X=b;

X=c;
开发者_StackOverflow中文版
X=d;

X=e;

or, at least:

X=a,b,c,d,e;

I'm wondering about how to have results ordered by depth levels as output, something like:

X=[a];

X=[b,c];

X=[d,e];

or, in the best case, something like:

X=[ [a] , [b,c] , [d,e] ];

Help!

I have a solution, but it's not particularly efficient. I implemented the tree as a bunch of three element lists, like [Element, Left, Right], but it should work the same.

% returns a list of nodes at the given level of the tree
level( [], _, [] ).
level( [Element, _, _], 0, [Element] ) :- !.
level( [_, Left, Right], N, Result ) :-
    NewN is N - 1,
    level( Left, NewN, LeftResult ),
    level( Right, NewN, RightResult ),
    append( LeftResult, RightResult, Result ).

% does a bfs, returning a list of lists, where each inner list
% is the nodes at a given level
bfs( Tree, Result ) :-
    level( Tree, 0, FirstLevel ), !,
    bfs( Tree, 1, FirstLevel, [], BFSReverse ),
    reverse( BFSReverse, Result ).
bfs( _, _, [], Accum, Accum ) :- !.
bfs( Tree, Num, LastLevel, Accum, Result ) :-
    level( Tree, Num, CurrentLevel ), !,
    NewNum is Num + 1,
    bfs( Tree, NewNum, CurrentLevel, [LastLevel|Accum], Result ).

It should be possible to do this in O(n), but this is O(n^2). I started to work on another solution that returns the level of each element in O(n), but I'm not sure how to transform that list to the solution format in O(n) without resorting to assert/retract.

Better solution, this time O(n). It's still a bit ugly because I separated the actual BFS from the solution processing, but that should do it.

bfs2( Tree, Result ) :-
    bfs_queue( [[Tree, 0]], Queue ),
    queue_to_result( Queue, Result ).
bfs_queue( [], [] ) :- !.
bfs_queue( [[[],_]|Rest], RestResult ) :-
    !, bfs_queue( Rest, RestResult ).
bfs_queue( [[[Element, Left, Right], Level]|Rest], [[Element,Level]|RestResult] ) :-
    NextLevel is Level + 1,
    append( Rest, [[Left, NextLevel], [Right, NextLevel]], NewQueue ), !,
    bfs_queue( NewQueue, RestResult ).

process_level( [[Item, Level]|Rest], Level, [Item|RestResult], OutOfLevel ) :-
    !, process_level( Rest, Level, RestResult, OutOfLevel ).
process_level( OutOfLevel, _, [], OutOfLevel ) :- !.
queue_to_result( Queue, Result ) :-
    !, queue_to_result( Queue, 0, Result ).
queue_to_result( [], _, [] ) :- !.
queue_to_result( Queue, Level, [Current|Result] ) :-
    !, process_level( Queue, Level, Current, NewQueue ),
    NewLevel is Level + 1,
    queue_to_result( NewQueue, NewLevel, Result ).

Again, I represented trees as three element lists.