Menu Close

Máxima distancia en árbol

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 (Eq, Show)

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      1
     / \    / \
    3   9  2   6

se puede representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 9))
                  (N 1 (H 2) (H 6))

La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.

Definir la función

   maximaDistancia :: (Num a, Ord a) => Arbol a -> a

tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,

   maximaDistancia ejArbol                                     ==  9
   maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1  (H 2) (H 6)))  ==  7
   maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6)))  ==  8

Soluciones

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show
 
ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 9))
               (N 1 (H 2) (H 6))
 
 
maximaDistancia :: (Num a, Ord a) => Arbol a -> a
maximaDistancia (H _)     = 0
maximaDistancia (N x i d) = maximum [abs (x - raiz i)
                                    , maximaDistancia i
                                    , abs (x - raiz d)
                                    , maximaDistancia d]
 
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x
Inicial

4 soluciones de “Máxima distancia en árbol

  1. menvealer
    maximaDistancia :: (Num a, Ord a) => Arbol a -> a
    maximaDistancia (H a)     = 0
    maximaDistancia (N a i d) =
      maximum (map abs (map resta (padreEHijos (N a i d))))
     
    valor :: Arbol a -> a
    valor (H a)     = a
    valor (N a i d) = a
     
    padreEHijos :: (Num a, Ord a) => Arbol a -> [(a,a)]
    padreEHijos (H a)     = []
    padreEHijos (N a i d) =
      (a,valor i) : padreEHijos i ++ (a,valor d) : padreEHijos d
     
    tuplar :: (Num a, Ord a) => (a,a) -> [a]
    tuplar (x,y) = [x,y]
     
    resta :: (Num a, Ord a) => (a,a) -> a
    resta (x,y) = x - y
  2. antnavoro
    maximaDistancia :: (Num a, Ord a) => Arbol a -> a
    maximaDistancia (H _) = 0
    maximaDistancia (N a b c) = maximum [ abs (a-valor b)
                                        , abs (a-valor c)
                                        , maximaDistancia b
                                        , maximaDistancia c ]
      where valor (H a) = a
            valor (N a _ _) = a
  3. jaibengue
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a)
                 deriving (Eq, Show)
     
    maximaDistancia :: (Num a, Ord a) => Arbol a -> a
    maximaDistancia (N a (N b r s) (N c t u)) =
      maximum [ abs (a-b)
              , abs (a-c)
              , maximaDistancia (N b r s)
              , maximaDistancia (N c t u)]
    maximaDistancia (N a (N b r s) (H c)) =
      maximum [ abs (a-b)
              , abs (a-c)
              , maximaDistancia (N b r s)]
    maximaDistancia (N a (H b) (N c t u)) =
      maximum [ abs (a-b)
              , abs (a-c)
              , maximaDistancia (N c t u)]
    maximaDistancia (N a (H b) (H c)) =
      maximum [ abs (a-b)
              , abs (a-c)]
    maximaDistancia (H a) = 0
  4. alvblamol
    maximaDistancia :: (Num a, Ord a) => Arbol a -> a
    maximaDistancia (N a b c) = maximum (distancias (N a b c))
    maximaDistancia (H a)     = 0
     
    distancias :: Num a => Arbol a -> [a]
    distancias (H a) = []
    distancias (N a b c) = [ abs (a - valor b)
                           , abs (a - valor c)] ++
                           distancias b ++
                           distancias c
     
    valor :: Arbol a -> a
    valor (N a b c) = a
    valor (H a)     = a

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.