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