Menu Close

Relación definida por un árbol

José A. Alonso,

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
Posted in Inicial
Tagged ,

6 Comments

  1. alerodrod5
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder

    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
    Responder 
    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.