Prolog obtenir des éléments dans différentes listes avec BFS

Question

Je suis nouveau au prologue et pour améliorer mes compétences, je suis en train de faire de l'exercice. En ce moment je suis coincé avec un BFS, laisser supposer l'arbre est quelque chose comme ceci:

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

après ma requête, j'ai quelque chose comme

X=a; 

X=b; 

X=c; 

X=d; 

X=e; 

ou, au moins:

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

Je me demande sur la façon d'obtenir des résultats ordonnés par des niveaux de profondeur que la production, quelque chose comme:

X=[a]; 

X=[b,c]; 

X=[d,e]; 

ou, dans le meilleur des cas, quelque chose comme:

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

Aide!

Answer 1

Meilleure solution, cette fois O (n). C'est encore un peu moche parce que j'ai séparé le BFS réel du traitement de la solution, mais cela devrait le faire.

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

De nouveau, j'ai représenté les arbres comme trois listes d'éléments.

Answer 2

J'ai une solution, mais ce n'est pas particulièrement efficace. J'ai implémenté l'arbre comme un ensemble de trois listes d'éléments, comme [Element, Left, Right], mais cela devrait fonctionner de la même manière.

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

Il devrait être possible de le faire dans O (n), mais c'est O (n^2). J'ai commencé à travailler sur une autre solution qui retourne le niveau de chaque élément dans O (n), mais je ne suis pas sûr de savoir comment transformer cette liste au format de la solution dans O (n) sans avoir recours à assert/retract.