Convertir lista de adyacencias a formato recursivo
Dado un árbol binario en un formato de lista de adyacencias como [1-8,1-2,…]
Los elementos en la lista no están en un orden en particular.
Dado el nodo raíz del árbol se necesita convertir la lista en un formato recursivo t(L,Root,R). Donde L y R son árboles en sí mismos o nulos.
Esto es lo que he intentado:
% convertir árbol binario desde lista de adyacencias a formato recursivo de términos.
% make_tree(ListaAdyacencias, Raíz, Árbol)
make_tree([],Raíz,t(nil,Raíz,nil)):-!.
make_tree([Raíz-X],Raíz,t(X,Raíz,nil)).
make_tree([Raíz-X],Raíz,t(nil,Raíz,X)):-!.
make_tree(_,nil,nil):-!.
make_tree(N,Raíz,t(L,Raíz,R)):-
find_kids(N,Raíz,C,S),
reorder(C,[C1,C2]),
make_tree(S,C1,L), make_tree(S,C2,R).
% reordenar 2 de 2
reorder([X,Y],[Y,X]).
reorder([X,Y],[X,Y]).
% encontrar hijos y removerlos de la lista de nodos
find_kids(L,Raíz,[C1,C2],R):-
find_children(L,Raíz,[C1,C2|_],R).
find_children([Raíz-Y|Xs],Raíz,[Y|T],Acc):-
find_children(Xs,Raíz,T,Acc).
find_children([X-Y|Xs],Raíz,R,[X-Y|Acc]):-
X \= Raíz,
find_children(Xs,Raíz,R,Acc).
find_children([],_,[nil,nil],[]).
davy.ai
Explicación:
El código anterior primero verifica si la lista de adyacencia está vacía. Si lo está, devuelve un árbol con nil para L y R. Si la lista de adyacencia tiene solo un elemento, verifica si ese elemento es la raíz. Si lo es, devuelve un árbol con X como R y nil como L, o viceversa. Si no se encuentra la raíz, devuelve nil.
Si hay más de un elemento en la lista de adyacencia, llama al predicado find_kids para obtener los hijos de la raíz. Luego reordena los hijos, asumiendo que el hijo izquierdo viene antes que el hijo derecho. Luego llama recursivamente a make_tree en los hijos izquierdo y derecho.
El predicado find_children se utiliza para encontrar los hijos de un nodo dado la lista de adyacencia. Verifica si el primer elemento en la lista de adyacencia coincide con la raíz. Si lo hace, agrega el hijo a la lista y llama recursivamente a sí mismo en los elementos restantes en la lista de adyacencia. Si no coincide, agrega el nodo a un acumulador y llama recursivamente a sí mismo en los elementos restantes. Si la lista está vacía, devuelve nil para ambos hijos.
En general, este código convertirá una lista de adyacencia para un árbol binario a un formato recursivo utilizando Prolog.