Menu Close

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]
Medio

Una solución de “Caminos en un árbol binario

  1. Jesús Navas Orozco
    caminos :: Arbol -> [Camino]
    caminos H = [[]]
    caminos (N x y) = map (I:) (caminos x) ++ map (D:) (caminos y)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.