{"id":1907,"date":"2012-02-21T17:01:14","date_gmt":"2012-02-21T17:01:14","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1907"},"modified":"2014-02-09T20:37:59","modified_gmt":"2014-02-09T19:37:59","slug":"i1m2011-ejercicios-sobre-arboles-binarios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-sobre-arboles-binarios-en-haskell\/","title":{"rendered":"I1M2011: Ejercicios sobre \u00e1rboles binarios en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_19.hs\">19\u00aa relaci\u00f3n<\/a>. <\/p>\n<p> En esta relaci\u00f3n se plantean ejercicios sobre \u00e1rboles binarios. En concreto, se definen funciones para calcular:<\/p>\n<ul>\n<li> el n\u00famero de hojas de un \u00e1rbol,\n<li> el n\u00famero de nodos de un \u00e1rbol,\n<li> la profundidad de un \u00e1rbol,\n<li> el recorrido preorden de un \u00e1rbol,\n<li> el recorrido postorden de un \u00e1rbol,\n<li> el recorrido preorden de forma iterativa,\n<li> la imagen especular de un \u00e1rbol,\n<li> el sub\u00e1rbol de profundidad dada,\n<li> el \u00e1rbol infinito generado con un elemento y\n<li> el \u00e1rbol de profundidad dada cuyos nodos son iguales a un elemento.\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con los \u00e1rboles\r\n-- binarios definidos como sigue \r\n--    data Arbol a = Hoja \r\n--                 | Nodo a (Arbol a) (Arbol a)\r\n--                 deriving (Show, Eq)\r\n-- En los ejemplos se usar\u00e1 el siguiente \u00e1rbol\r\n--    arbol = Nodo 9\r\n--                   (Nodo 3 \r\n--                         (Nodo 2 Hoja Hoja) \r\n--                         (Nodo 4 Hoja Hoja)) \r\n--                   (Nodo 7 Hoja Hoja)\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol a = Hoja \r\n             | Nodo a (Arbol a) (Arbol a)\r\n             deriving (Show, Eq)\r\n\r\narbol = Nodo 9\r\n               (Nodo 3 \r\n                     (Nodo 2 Hoja Hoja) \r\n                     (Nodo 4 Hoja Hoja)) \r\n               (Nodo 7 Hoja Hoja)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    nHojas :: Arbol a -> Int\r\n-- tal que (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> nHojas arbol\r\n--    6\r\n-- ---------------------------------------------------------------------\r\n\r\nnHojas :: Arbol a -> Int\r\nnHojas Hoja         = 1\r\nnHojas (Nodo x i d) = nHojas i + nHojas d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    nNodos :: Arbol a -> Int\r\n-- tal que (nNodos x) es el n\u00famero de nodos del \u00e1rbol x. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> nNodos arbol\r\n--    5\r\n-- ---------------------------------------------------------------------\r\n\r\nnNodos :: Arbol a -> Int\r\nnNodos Hoja         = 0\r\nnNodos (Nodo x i d) = 1 + nNodos i + nNodos d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    profundidad :: Arbol a -> Int\r\n-- tal que (profundidad x) es la profundidad del \u00e1rbol x. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> profundidad arbol\r\n--    3\r\n-- ---------------------------------------------------------------------\r\n\r\nprofundidad :: Arbol a -> Int\r\nprofundidad Hoja = 0\r\nprofundidad (Nodo x i d) = 1 + max (profundidad i) (profundidad d)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    preorden :: Arbol a -> [a]\r\n-- tal que (preorden x) es la lista correspondiente al recorrido\r\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\r\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\r\n-- sub\u00e1rbol derecho. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> preorden arbol\r\n--    [9,3,2,4,7]\r\n-- ---------------------------------------------------------------------\r\n\r\npreorden :: Arbol a -> [a]\r\npreorden Hoja         = []\r\npreorden (Nodo x i d) = x : (preorden i ++ preorden d)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    postorden :: Arbol a -> [a]\r\n-- tal que (postorden x) es la lista correspondiente al recorrido\r\n-- postorden del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol\r\n-- izquierdo, a continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz\r\n-- del \u00e1rbol. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> postorden arbol\r\n--    [2,4,3,7,9]\r\n-- ---------------------------------------------------------------------\r\n\r\npostorden :: Arbol a -> [a]\r\npostorden Hoja         = []\r\npostorden (Nodo x i d) = postorden i ++ postorden d ++ [x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir, usando un acumulador, la funci\u00f3n\r\n--    preordenIt :: Arbol a -> [a]\r\n-- tal que (preordenIt x) es la lista correspondiente al recorrido\r\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\r\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\r\n-- sub\u00e1rbol derecho. Por ejemplo,\r\n--    ghci> arbol\r\n--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)\r\n--    ghci> preordenIt arbol\r\n--    [9,3,2,4,7]\r\n-- Nota: No usar (++) en la definici\u00f3n\r\n-- ---------------------------------------------------------------------\r\n\r\npreordenIt :: Arbol a -> [a]\r\npreordenIt x = preordenItAux x []\r\n    where preordenItAux Hoja xs         = xs\r\n          preordenItAux (Nodo x i d) xs = \r\n              x : preordenItAux i (preordenItAux d xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    espejo :: Arbol a -> Arbol a\r\n-- tal que (espejo x) es la imagen especular del \u00e1rbol x. Por ejemplo,\r\n--    ghci> espejo arbol\r\n--    Nodo 9 \r\n--         (Nodo 7 Hoja Hoja) \r\n--         (Nodo 3 \r\n--               (Nodo 4 Hoja Hoja) \r\n--               (Nodo 2 Hoja Hoja))\r\n-- ---------------------------------------------------------------------\r\n\r\nespejo :: Arbol a -> Arbol a\r\nespejo Hoja         = Hoja\r\nespejo (Nodo x i d) = Nodo x (espejo d) (espejo i)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. La funci\u00f3n take est\u00e1 definida por\r\n--    take :: Int -> [a] -> [a]\r\n--    take 0            = []\r\n--    take (n+1) []     = []\r\n--    take (n+1) (x:xs) = x : take n xs\r\n-- Definir la funci\u00f3n \r\n--    takeArbol ::  Int -> Arbol a -> Arbol a\r\n-- tal que (takeArbol n t) es el sub\u00e1rbol de t de profundidad n. Por\r\n-- ejemplo,\r\n--    ghci> takeArbol 0 (Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja))\r\n--    Hoja\r\n--    ghci> takeArbol 1 (Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja))\r\n--    Nodo 6 Hoja Hoja\r\n--    ghci> takeArbol 2 (Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja))\r\n--    Nodo 6 Hoja (Nodo 7 Hoja Hoja)\r\n--    ghci> takeArbol 3 (Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja))\r\n--    Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja)\r\n--    ghci> takeArbol 4 (Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja))\r\n--    Nodo 6 Hoja (Nodo 7 (Nodo 5 Hoja Hoja) Hoja)\r\n-- ---------------------------------------------------------------------\r\n \r\ntakeArbol :: Int -> Arbol a -> Arbol a\r\ntakeArbol 0     _  = Hoja\r\ntakeArbol _ Hoja   = Hoja\r\ntakeArbol n (Nodo x i d) = \r\n    Nodo x (takeArbol (n-1) i) (takeArbol (n-1) d)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. La funci\u00f3n\r\n--    repeat :: a -> [a]\r\n-- est\u00e1 definida de forma que (repeat x) es la lista formada por\r\n-- infinitos elementos x. Por ejemplo,\r\n--    repeat 3  ==  [3,3,3,3,3,3,3,3,3,3,3,3,3,...\r\n-- La definici\u00f3n de repeat es\r\n--    repeat x = xs where xs = x:xs\r\n-- Definir la funci\u00f3n\r\n--    repeatArbol :: a -> Arbol a\r\n-- tal que (repeatArbol x) es es \u00e1rbol con infinitos nodos x. Por\r\n-- ejemplo, \r\n--    ghci> takeArbol 0 (repeatArbol 3)\r\n--    Hoja\r\n--    ghci> takeArbol 1 (repeatArbol 3)\r\n--    Nodo 3 Hoja Hoja\r\n--    ghci> takeArbol 2 (repeatArbol 3)\r\n--    Nodo 3 (Nodo 3 Hoja Hoja) (Nodo 3 Hoja Hoja)\r\n-- ---------------------------------------------------------------------\r\n\r\nrepeatArbol :: a -> Arbol a\r\nrepeatArbol x = Nodo x t t\r\n                where t = repeatArbol x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. La funci\u00f3n \r\n--    replicate :: Int -> a -> [a]\r\n-- est\u00e1 definida por \r\n--    replicate n = take n . repeat\r\n-- es tal que (replicate n x) es la lista de longitud n cuyos elementos\r\n-- son x. Por ejemplo,\r\n--    replicate 3 5  ==  [5,5,5]\r\n-- Definir la funci\u00f3n \r\n--    replicateArbol :: Int -> a -> Arbol a\r\n-- tal que (replicate n x) es el \u00e1rbol de profundidad n cuyos nodos son\r\n-- x. Por ejemplo,\r\n--    ghci> replicateArbol 0 5\r\n--    Hoja\r\n--    ghci> replicateArbol 1 5\r\n--    Nodo 5 Hoja Hoja\r\n--    ghci> replicateArbol 2 5\r\n--    Nodo 5 (Nodo 5 Hoja Hoja) (Nodo 5 Hoja Hoja)\r\n-- ---------------------------------------------------------------------\r\n\r\nreplicateArbol :: Int -> a -> Arbol a\r\nreplicateArbol n = takeArbol n . repeatArbol\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la 19\u00aa relaci\u00f3n. En esta relaci\u00f3n se plantean ejercicios sobre \u00e1rboles binarios. En concreto, se definen funciones para calcular: el n\u00famero de hojas de un \u00e1rbol, el n\u00famero de nodos de un \u00e1rbol,&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[1],"tags":[295],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1907"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1907"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1907\/revisions"}],"predecessor-version":[{"id":2848,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1907\/revisions\/2848"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1907"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1907"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1907"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}