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 2 3 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
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles los árboles anteriores se puede representar por
|
1 2 3 4 |
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
|
1 |
esBinarioCompleto :: Arbol t -> Bool |
tal que (esBinarioCompleto a) se verifica si a es un árbol binario completo. Por ejemplo,
|
1 2 3 |
esBinarioCompleto ej1 == True esBinarioCompleto ej2 == False esBinarioCompleto ej3 == False |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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 |