Menu Close

Árboles binarios completos

Un árbol binario completo es un árbol en el que cada nodo tiene cero o dos hijos. Por ejemplo, el primero de los siguientes árboles es un árbol binario completo pero los otros no lo son

           1              1            1    
         /   \          /   \        / | \ 
        2     3        2     3      2  7  3
       / \            /            / \      
      4   5          4            4   5

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
     deriving Show

Por ejemplo, los árboles los árboles anteriores se puede representar por

   ej1, ej2, ej3 :: Arbol Int
   ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 []]
   ej2 = N 1 [N 2 [N 4 []], N 3 []]
   ej3 = N 1 [N 2 [N 4 [], N 5 []], N 7 [], N 3 []]

Definir la función

   esBinarioCompleto :: Arbol t -> Bool

tal que (esBinarioCompleto a) se verifica si a es un árbol binario completo. Por ejemplo,

   esBinarioCompleto ej1  ==  True
   esBinarioCompleto ej2  ==  False
   esBinarioCompleto ej3  ==  False

Soluciones

data Arbol a = N a [Arbol a]
  deriving Show
 
ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 []]
ej2 = N 1 [N 2 [N 4 []], N 3 []]
ej3 = N 1 [N 2 [N 4 [], N 5 []], N 7 [], N 3 []]
 
esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ []) = True
esBinarioCompleto (N x as) = length as `elem` [0,2] 
                             && all esBinarioCompleto as
Inicial

6 soluciones de “Árboles binarios completos

  1. antnavoro
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto (N _ xs) =  and $ elem (length xs) [0,2] : map esBinarioCompleto xs
  2. angruicam1
    data Arbol a = N {rootLabel :: a,
                      subForest :: [Arbol a]}
      deriving Show
     
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto a =
      all (all ((||) . (== 2) <*> (== 0)))
      . map (map (length . subForest))
      . takeWhile (not . null)
      . iterate (concatMap subForest) $ [a]
  3. albcarcas1
     
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto (N _ xs) = (null xs || length xs == 2) && 
                                 and[esBinarioCompleto x | x <- xs]
  4. alerodrod5
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto (N _ xs) = (length xs == 2 || length xs == 0) &&
                                 and (map esBinarioCompletoA4 xs)
  5. jaibengue
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto (N _ []) = True
    esBinarioCompleto (N _ h)  = length h == 2 && and (map esBinarioCompleto h)
  6. Chema Cortés
    data Arbol a = N a [Arbol a]
      deriving Show
     
    esBinarioCompleto :: Arbol t -> Bool
    esBinarioCompleto (N _ [])       = True
    esBinarioCompleto (N _ xs@[_,_]) = all esBinarioCompleto xs
    esBinarioCompleto _              = False

Escribe tu solución

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