Menu Close

Relación definida por un á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      2
     / \    / \
    3   5  2   0

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 5))
                  (N 2 (H 2) (H 0))

Un árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y. Por ejemplo, la relación definida por el árbol anterior es [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)].

Definir la función

   relacionDelArbol :: Arbol a -> [(a,a)]

tal que (relacionDelArbol a) es la relación binaria definida por el árbol a. Por ejemplo,

   λ> relacionDelArbol ejArbol
   [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))
   [(10,8),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
   [(10,8),(8,3),(8,5),(10,2)]
   λ> relacionDelArbol (H 10)
   []

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 5))
               (N 2 (H 2) (H 0))
 
relacionDelArbol :: Arbol a -> [(a,a)]
relacionDelArbol (H _)     = []
relacionDelArbol (N x i d) = ((x,raiz i) : relacionDelArbol i) ++ 
                             ((x,raiz d) : relacionDelArbol d)
 
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x
Inicial

6 soluciones de “Relación definida por un árbol

  1. alerodrod5
    data Arbol a = H a
                    | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    ejArbol :: Arbol Int
    ejArbol = N 10 (N 8 (H 3) (H 5))
                   (N 2 (H 2) (H 0))
     
    relacionDelArbol :: Arbol a -> [(a,a)]
    relacionDelArbol (H x) = []
    relacionDelArbol (N x a1 a2)= ((x,valor a1) : relacionDelArbol a1) ++
                                  ((x,valor a2) : relacionDelArbol a2)
      where valor (H x )     = x
            valor (N x _ _ ) = x
  2. agumaragu1
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a)
          deriving (Eq, Show)
     
    ejArbol :: Arbol Int
    ejArbol = N 10 (N 8 (H 3) (H 5))
                   (N 2 (H 2) (H 0))
     
    relacionDelArbol :: Arbol a -> [(a,a)]
    relacionDelArbol (H _)       = []
    relacionDelArbol (N x ry rz) = (par x ry : relacionDelArbol ry) ++
                                   (par x rz : relacionDelArbol rz)
      where par a (H x)     = (a, x)
            par a (N x _ _) = (a, x)
  3. jaibengue
    data Arbol a = H a
                   | N a (Arbol a) (Arbol a)
                   deriving (Eq, Show)
     
    relacionDelArbol :: Arbol a -> [(a,a)]
    relacionDelArbol (N a (N b r s) (N c t u)) =
      (a,b) : relacionDelArbol (N b r s) ++
      (a,c) : relacionDelArbol (N c t u)
    relacionDelArbol (N a (N b r s) (H c)) =
      (a,b) : relacionDelArbol (N b r s) ++ [(a,c)]
    relacionDelArbol (N a (H b) (N c t u)) =
      [(a,b),(a,c)] ++ relacionDelArbol (N c t u)
    relacionDelArbol (N a (H b) (H c)) = [(a,b),(a,c)]
    relacionDelArbol (H a) = []
  4. carbremor
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    relacionDelArbol :: Arbol a -> [(a,a)] 
    relacionDelArbol (H _) = [] 
    relacionDelArbol (N v i d) = [(v, getVal i), (v, getVal d)] ++
                                 relacionDelArbol i ++
                                 relacionDelArbol d
     
    getVal (N v _ _) = v
    getVal (H v)     = v
     
    -- relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
    -- [(10,8),(10,2),(8,3),(8,5)]
    -- (0.01 secs, 98,344 bytes)
  5. josejuan

    Por diversión, podemos transformar los árboles en listas de forma general y fijar selectores tales que las estructuras lineales identifiquen de forma separada a los padres y a los hijos, por lo que podemos hacer zip de ambas.

    import Data.Monoid ((<>))
     
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a)
      deriving (Eq, Show)
     
    recorre :: Monoid b => (a -> b) -> (a -> b) -> Arbol a -> b
    recorre f _ (H x    ) = f x
    recorre f g (N x u v) = f x <> g x <> recorre f g u <> g x <> recorre f g v
     
    relacionDelArbol :: Arbol a -> [(a, a)]
    relacionDelArbol a = zip (recorre i t a) (tail $ recorre t i a)
      where t x = [x]
            i _ = [ ]
  6. menvealer
    relacionDelArbol :: Arbol a -> [(a,a)]
    relacionDelArbol (H a) = []
    relacionDelArbol (N a i d) = (a,nodoUHojaPpal i) : relacionDelArbol i ++
                                 (a,nodoUHojaPpal d) : relacionDelArbol d
     
    nodoUHojaPpal :: Arbol a -> a
    nodoUHojaPpal (H a)     = a
    nodoUHojaPpal (N a i d) = a

Escribe tu solución

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