CODEWITHSUNDEEP
prolog
Kirby
Kirby

Reputation: 455

return all levels of a binarytree in prolog

I'm trying to get a program to return the levels of a BT in the way of a list and I'm stuck at this: 

nivel(nodo(L,Root,R)) :- nivel(nodo(L,Root,R),X),writeln(X).
nivel(vacio,[]).
nivel(nodo(L,Root,R),[Root|T]) :- nivel(L,T),nivel(R,T),writeln(T).

An example input-output of what I'm trying is:

nivel(nodo(nodo(vacio,4,vacio), t, nodo(vacio,r,vacio))
  X =[t]
  X =[4,r]

problem is I don't know how to make the program get the new Roots. Any ideas? Also, thanks in advance!

Upvotes: 1

Views: 1121

Answers (2)

user206428
user206428

Reputation:

Quite a tricky one for Prolog, but here's one solution to consider which provides a true level-order (L-R breadth-first) tree traversal:

nivel(nodo(L,Root,R), Level) :-
    depth_value_pairs(nodo(L,Root,R), 0, DVPairs),
    keylistmerge(DVPairs, Groups),
    maplist(keyvalue, Groups, _, Values),
    member(Level, Values).

nivel/2 is your entry predicate. Basically, it uses depth_value_pairs/3, which generates solutions of the form Depth-Value (e.g., 0-t to represent the root node t at ply depth 0, or 1-4 to represent the node 4 at ply depth 1, etc.). Then, it uses keylistmerge/2 to merge the list all depth-value pairs into depth groups, e.g., [0-[t], 1-[4,t], ...]. Then, the maplist(keyvalue... call busts the Depth- parts from the lists, and the final predicate call member/2 selects each list to bind to the output Level.

Here are the other predicate definitions:

depth_value_pairs(vacio, _, []).
depth_value_pairs(nodo(L, Root, R), Depth, [Depth-Root|Level]) :-
    NextLevel is Depth + 1,
    depth_value_pairs(L, NextLevel, LL),
    depth_value_pairs(R, NextLevel, RL),
    append(LL, RL, Level).

keyvalue(K-V, K, V).

keylistmerge(KVL, MKVL) :-
    keysort(KVL, [K-V|KVs]),
    keylistmerge([K-V|KVs], K, [], MKVL).
keylistmerge([], K, Acc, [K-Acc]).
keylistmerge([K0-V|KVs], K, Acc, MKVL) :-
    K == K0, !,
    append(Acc, [V], NewAcc),
    keylistmerge(KVs, K, NewAcc, MKVL).
keylistmerge([K0-V|KVs], K, Acc, [K-Acc|MKVs]) :-
    keylistmerge(KVs, K0, [V], MKVs).

Exercising this gives us:

?- nivel(nodo(nodo(vacio,4,nodo(vacio,5,vacio)), t, nodo(vacio,r,vacio)), Level).
Level = [t] ;
Level = [4, r] ;
Level = [5] ;
false.

Note that we rely on the built-in keysort/2 to be order-preserving (stable) so as to preserve the L-R order of nodes in the binary tree.

Upvotes: 1

gusbro
gusbro

Reputation: 22585

Here goes a solution, it traverses the tree once an builds a list of the items in each level.

nivel(Arbol, SubNivel):-
  nivel(Arbol, [], [], Items),
  member(SubNivel, Items),
  SubNivel \= [].

nivel(vacio, Items, SubNiveles, [Items|SubNiveles]).
nivel(nodo(Izq, Item, Der), Items, [], [[Item|Items]|NSubNiveles]):-
  nivel(Izq, [], [], [MSubItems|MSubNiveles]),
  nivel(Der, MSubItems, MSubNiveles, NSubNiveles).
nivel(nodo(Izq, Item, Der), Items, [SubItems|SubNiveles], [[Item|Items]|NSubNiveles]):-
  nivel(Izq, SubItems, SubNiveles, [MSubItems|MSubNiveles]),
  nivel(Der, MSubItems, MSubNiveles, NSubNiveles).

The second clause of nivel/4 is a hack due to the fact that the algorithm does not know in advance the height of the tree.

Test case:

?- nivel(nodo(nodo(nodo(nodo(vacio,f,vacio),e,nodo(vacio,g,vacio)),b,vacio),a,nodo(vacio,c,nodo(vacio,d,vacio))), X).
X = [a] ;     --> Root
X = [c, b] ;  --> First Level
X = [d, e] ;  --> Second Level
X = [g, f] ;  --> Third Level

Upvotes: 1

Related Questions