Menu Close

Ancestro común más bajo

El tipo de los árboles binarios se define por

   data Arbol = H Int
              | N Int Arbol Arbol

Por ejemplo, el árbol

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

se define por

   ejArbol :: Arbol
   ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

   ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

   ancestroComunMasBajo ejArbol 4 1  ==  3
   ancestroComunMasBajo ejArbol 1 6  ==  5
   ancestroComunMasBajo ejArbol 6 9  ==  7

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol
 
ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))
 
-- 1ª definición
-- =============
 
ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo1 a x y =
  head [u | u <- xs, u `elem` ys]
  where xs = ancestros a x
        ys = ancestros a y
 
-- (ancestros a x) es la lista de los ancestros de x en el árbol
-- ordenado a, ordenada por profundidad. Por ejemplo,
--    ancestros ejArbol 1 ==  [3,5]
--    ancestros ejArbol 3 ==  [5]
--    ancestros ejArbol 5 ==  []
--    ancestros ejArbol 9 ==  [7,5]
ancestros :: Arbol -> Int -> [Int]
ancestros a y = aux a y []
  where aux (H _)     _ zs = zs
        aux (N x i d) y zs 
          | x == y    = zs
          | y < x     = aux i y (x:zs)
          | otherwise = aux d y (x:zs)
 
-- 2ª definición
-- =============
 
ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo2 (N z i d) x y 
  | x < z && y < z = ancestroComunMasBajo2 i x y 
  | x > z && y > z = ancestroComunMasBajo2 d x y 
  | otherwise      = z
Medio

4 soluciones de “Ancestro común más bajo

  1. angruicam1
    data Arbol = H Int
               | N Int Arbol Arbol
     
    ejArbol :: Arbol
    ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))
     
    ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
    ancestroComunMasBajo (N a i d) x y
      | (a > x && a < y) || (a < x && a > y) = a
      |  a > x && a > y                      = ancestroComunMasBajo i x y
      |  otherwise                           = ancestroComunMasBajo d x y
  2. alerodrod5
    data Arbol = H Int
               | N Int Arbol Arbol
     
    ejArbol :: Arbol
    ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))
     
    elementos :: Arbol -> [Int]
    elementos (H x) = [x]
    elementos (N x a1 a2) = x : (elementos a1) ++ (elementos a2)
     
    ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
    ancestroComunMasBajo (H z) x y
      | x==y && z==x = z
      | otherwise = error "Al menos uno de los valores no pertenece al arbol"
     
    ancestroComunMasBajo a@(N x a1 a2) y z
      | y `elem` elementos a && z `elem` elementos a = aux a y z
      | otherwise = error "Al menos uno de los valores no pertenece al arbol"
      where aux (N x a1 a2) y z
              | y <= x && z >= x || z <= x && y >= x = x
              | y <  x && z <  x = ancestroComunMasBajo a1 y z
              | otherwise = ancestroComunMasBajo a2 y z
  3. urbguigui
    ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
    ancestroComunMasBajo (H n) x y = n
    ancestroComunMasBajo (N n a1 a2 ) x y 
      | elem x (hojas a2) && elem y (hojas a2)  = ancestroComunMasBajo a2 x y
      | elem x (hojas a1) && elem y (hojas a1)  = ancestroComunMasBajo a1 x y
      | otherwise                               = n
     
    hojas :: Arbol -> [Int]
    hojas (H n)       = [n]
    hojas (N n a1 a2) = [n]++  hojas a1++ hojas a2
  4. Álvaro Gutiérrez
    ancestros a x =
      reverse (init (head (filter (xs->(last xs)==x)
                                  (caminos a))))
     
    caminos (H a) = [[a]]
    caminos (N n a1 a2) =
      map (e->n:e) (caminos a1) ++
      map (e->n:e) (caminos a2)
     
    ancestroComunMasBajo a x y =
      head [z | z <- ancestros a x, elem z (ancestros a y)]

Escribe tu solución

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