Prolog bekommen Elemente in verschiedenen Listen mit BFS

Question

Ich bin neu auf Prolog und meine Fähigkeiten zu verbessern ich versuche, etwas Bewegung zu machen. Im Moment arbeite ich mit einem BFS bin stecken, lassen vermuten, der Baum so etwas wie dieses:

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

nach meiner Anfrage habe ich so etwas wie

X=a; 

X=b; 

X=c; 

X=d; 

X=e; 

oder zumindest:

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

ich frage mich, wie durch Tiefenebenen als Ausgang, so etwas wie geordnete Ergebnisse haben:

X=[a]; 

X=[b,c]; 

X=[d,e]; 

oder, im besten Fall, so etwas wie:

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

Hilfe!

Answer 1

Bessere Lösung, diesmal O (n). Es ist immer noch ein bisschen hässlich, weil ich die tatsächliche BFS von der Lösungsverarbeitung getrennt habe, aber das sollte es tun.

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). 

Wieder stellte ich Bäume als drei Elementlisten dar.

Answer 2

Ich habe eine Lösung, aber es ist nicht besonders effizient. Ich habe den Baum als eine Reihe von drei Elementlisten implementiert, wie [Element, Links, Rechts], aber es sollte genauso funktionieren.

% 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). 

Es sollte möglich sein, dies in O (n) zu tun, aber das ist O (n^2). Ich begann, an einer anderen Lösung zu arbeiten, die die Ebene jedes Elements in O (n) zurückgibt, aber ich bin mir nicht sicher, wie ich diese Liste in das Lösungsformat in O (n) umwandeln kann, ohne auf Assert/Retract zurückgreifen zu müssen.