вернуть все уровни двоичного дерева в прологе

Question

Я пытаюсь заставить программу возвращать уровни BT в виде списка, и я застрял в этом:

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

Пример ввода-вывода того, что я пытаюсь сделать так:

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

проблема в том, что я не знаю, как заставить программу получить новые корни. Есть идеи? Также заранее спасибо!

Answer 1

Здесь идет решение, оно пересекает дерево, как только строит список элементов на каждом уровне.

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

Второй пункт nivel / 4 является хаком из-за того, что алгоритмзаранее не знает высоту дерева.

Контрольный пример:

?- 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

Answer 2

Довольно сложно для Пролога, но вот одно решение, которое нужно рассмотреть, которое обеспечивает истинный порядок уровней (LR в ширину) обход дерева:

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Ваш предикат входа.В основном он использует depth_value_pairs/3, который генерирует решения в форме Depth-Value (например, 0-t для представления корневого узла t на глубине слоя 0 или 1-4 для представления узла 4 вглубина слоя 1 и т. д.).Затем он использует keylistmerge/2 для объединения списка всех пар значений глубины в группы глубин, например, [0-[t], 1-[4,t], ...].Затем вызов maplist(keyvalue... удаляет части Depth- из списков, а последний вызов предиката member/2 выбирает каждый список для привязки к выходу Level.

Вот и другие определения предикатов:

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

Выполнение этого дает нам:

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

Обратите внимание, что мы полагаемся на встроенный keysort/2, чтобысохранение порядка ( stable ), чтобы сохранить порядок LR узлов в двоичном дереве.