Paridad de un árbol
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
5 / \ / \ 9 7 / \ / \ 1 4 6 8 |
se puede representar por
|
1 |
N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8)) |
Decimos que un árbol binario es par si la mayoría de sus valores (en nodos u hojas) son pares e impar en caso contrario.
Para representar la paridad se define el tipo Paridad
|
1 |
data Paridad = Par | Impar deriving (Eq, Show) |
Definir la función
|
1 |
paridad :: Arbol3 Int -> Paridad |
tal que (paridad a) es la paridad del árbol a. Por ejemplo,
|
1 2 |
paridad (N 8 (N 6 (H 3) (H 4)) (H 5)) == Par paridad (N 8 (N 9 (H 3) (H 4)) (H 5)) == Impar |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show data Paridad = Par | Impar deriving (Eq, Show) paridad :: Arbol Int -> Paridad paridad a | x > y = Par | otherwise = Impar where (x,y) = paridades a -- (paridades a) es un par (x,y) donde x es el número de valores pares -- en el árbol a e i es el número de valores impares en el árbol a. Por -- ejemplo, -- paridades (N (N (H 3) 6 (H 4)) 8 (H 5)) == (3,2) -- paridades (N (N (H 3) 9 (H 4)) 8 (H 5)) == (2,3) paridades :: Arbol Int -> (Int,Int) paridades (H x) | even x = (1,0) | otherwise = (0,1) paridades (N x i d) | even x = (1+a1+a2,b1+b2) | otherwise = (a1+a2,1+b1+b2) where (a1,b1) = paridades i (a2,b2) = paridades d |