Máxima distancia en árbol
Los árboles binarios con valores en las hojas y en los nodos se definen por
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) |
Por ejemplo, el árbol
1 2 3 4 5 6 |
10 / \ / \ 8 1 / \ / \ 3 9 2 6 |
se puede representar por
1 2 3 |
ejArbol :: Arbol Int ejArbol = N 10 (N 8 (H 3) (H 9)) (N 1 (H 2) (H 6)) |
La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.
Definir la función
1 |
maximaDistancia :: (Num a, Ord a) => Arbol a -> a |
tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,
1 2 3 |
maximaDistancia ejArbol == 9 maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1 (H 2) (H 6))) == 7 maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6))) == 8 |
Soluciones
[schedule expon=’2018-02-05′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 05 de febrero.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2018-02-05′ at=»06:00″]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show ejArbol :: Arbol Int ejArbol = N 10 (N 8 (H 3) (H 9)) (N 1 (H 2) (H 6)) maximaDistancia :: (Num a, Ord a) => Arbol a -> a maximaDistancia (H _) = 0 maximaDistancia (N x i d) = maximum [abs (x - raiz i) , maximaDistancia i , abs (x - raiz d) , maximaDistancia d] raiz :: Arbol a -> a raiz (H x) = x raiz (N x _ _) = x |
[/schedule]
4 Comentarios