我有一个解决方案,但它不是特别有效。我将树实现为一组三个元素列表,如 [Element, Left, Right],但它应该工作相同。
% 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 ).
应该可以在 O(n) 中执行此操作,但这是 O(n^2)。我开始研究另一种解决方案,该解决方案返回 O(n) 中每个元素的级别,但我不确定如何将该列表转换为 O(n) 中的解决方案格式而不诉诸断言/撤回。