Menu Close

Árboles binarios completos

José A. Alonso,

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. Responder
    antnavoro 
    esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ xs) =  and $ elem (length xs) [0,2] : map esBinarioCompleto xs
  2. Responder
    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. Responder
    albcarcas1 
     
esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ xs) = (null xs || length xs == 2) && 
                             and[esBinarioCompleto x | x <- xs]
  4. Responder
    alerodrod5 
    esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ xs) = (length xs == 2 || length xs == 0) &&
                             and (map esBinarioCompletoA4 xs)
  5. Responder
    jaibengue 
    esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ []) = True
esBinarioCompleto (N _ h)  = length h == 2 && and (map esBinarioCompleto h)
  6. Responder
    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.