序言请与BFS不同的列表元素
-
25-09-2019 - |
题
我是新的序言和提高我的技能我试图做一些锻炼。 在我套牢了BFS的那一刻,让我们假设树是这样的:
[tree(tree(tree(nil,b,nil),a,tree(tree(nil,d,nil),c,tree(nil,e,nil)))]
我的查询后,我有件事像
X=a;
X=b;
X=c;
X=d;
X=e;
,或至少:
X=a,b,c,d,e;
我想了解一下如何通过有层次的深度作为输出有序的结果,是这样的:
X=[a];
X=[b,c];
X=[d,e];
,或者在最好的情况下,是这样的:
X=[ [a] , [b,c] , [d,e] ];
帮助!
解决方案
更好的解决方案,这时间为O(n)。它仍然是一个有点难看,因为我从溶液中分离处理的实际BFS,但应该这样做。
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 ).
再次I表示树木三个元件列表。
其他提示
我有一个解决方案,但是它并不特别有效。我实现了树一堆三元列表,如[元素,左,右],但它应该工作一样。
% 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)的解格式。
不隶属于 StackOverflow