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 |
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 |
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 []] |
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 |
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 |
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 |
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
Se puede imprimir o compartir con
6 soluciones de “Árboles binarios completos”