Paridad de un árbol

José A. Alonso

01-12-2015

Los árboles binarios con valores en las hojas y en los nodos se definen por

data Arbol a = H a
              | N a (Arbol a) (Arbol a)
              deriving Show

Por ejemplo, el árbol

     5
    / \
   /   \
  9     7
 / \   / \
1   4 6   8

se puede representar por

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 nodos son pares e impar en caso contrario.

Para representar la paridad se define el tipo Paridad

data Paridad = Par | Impar deriving (Eq, Show)

Definir la función

paridad :: Arbol3 Int -> Paridad

tal que (paridad a) es la paridad del árbol a. Por ejemplo,

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

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