Caminos en un árbol binario
Los caminos en los árboles binarios
1 2 3 4 5 6 |
. . / \ / \ . . / \ / \ . . . . / \ / \ . . . . |
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
1 |
data Arbol = H | N Arbol Arbol |
los movimientos por
1 |
data Mov = I | D deriving Show |
y los caminos por
1 |
type Camino = [Mov] |
Definir la función
1 |
caminos :: Arbol -> [Camino] |
tal que (caminos a) es la lista de los caminos en el árbol binario a. Por ejemplo,
1 2 3 |
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
1 2 3 4 5 6 7 |
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] |
Un comentario