Ancestro común más bajo
El tipo de los árboles binarios se define por
1 2 |
data Arbol = H Int | N Int Arbol Arbol |
Por ejemplo, el árbol
1 2 3 4 5 6 |
5 / \ / \ 3 7 / \ / \ 1 4 6 9 |
se define por
1 2 |
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
1 |
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,
1 2 3 |
ancestroComunMasBajo ejArbol 4 1 == 3 ancestroComunMasBajo ejArbol 1 6 == 5 ancestroComunMasBajo ejArbol 6 9 == 7 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
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 |
4 Comentarios