Caminos en un árbol binario
Los caminos en los árboles binarios
. .
/ \ / \
. . / \
/ \ . .
. . / \ / \
. . . .
son [[I,I],[I,D],[D]] y [[I,I],[I,D],[D,I],[D,D]], donde I indica un movimiento hacia la izquierda y D uno hacia la derecha.
Los árboles binarios se pueden representar por
data Arbol = H | N Arbol Arbol
los movimientos por
data Mov = I | D deriving Show
y los caminos por
type Camino = [Mov]
Definir la función
caminos :: Arbol -> [Camino]
tal que (caminos a) es la lista de los caminos en el árbol binario a. Por ejemplo,
caminos (N (N H H) H) == [[I,I],[I,D],[D]] caminos (N (N H H) (N H H)) == [[I,I],[I,D],[D,I],[D,D]] caminos (N H (N (N H H) (N H H))) == [[I],[D,I,I],[D,I,D],[D,D,I],[D,D,D]]
Soluciones
data Arbol = H | N Arbol Arbol data Mov = I | D deriving Show type Camino = [Mov] caminos :: Arbol -> [Camino] caminos H = [[]] caminos (N i d) = [I:xs | xs <- caminos i] ++ [D:xs | xs <- caminos d]