{"id":5843,"date":"2017-11-17T17:07:25","date_gmt":"2017-11-17T16:07:25","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5843"},"modified":"2017-11-18T17:08:07","modified_gmt":"2017-11-18T16:08:07","slug":"i1m2017-ejercicios-sobre-arboles-binarios-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-ejercicios-sobre-arboles-binarios-en-haskell-1\/","title":{"rendered":"I1M2017: Ejercicios sobre \u00e1rboles binarios en Haskell (1)"},"content":{"rendered":"<p>En la tercera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los primeros ejercicios de la relaci\u00f3n 8 sobre \u00e1rboles binarios definidos como tipo de dato algebraico.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En esta relaci\u00f3n se presenta ejercicios sobre \u00e1rboles binarios\n-- definidos como tipos de datos algebraicos.\n-- \n-- Los ejercicios corresponden al tema 9 que se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\/temas\/tema-9.html\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Control.Monad\n\n-- ---------------------------------------------------------------------\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con los \u00e1rboles\n-- binarios definidos como sigue \n--    data Arbol a = H a\n--                 | N a (Arbol a) (Arbol a)\n--                 deriving (Show, Eq)\n-- Por ejemplo, el \u00e1rbol\n--         9 \n--        \/ \\\n--       \/   \\\n--      3     7\n--     \/ \\  \n--    2   4 \n-- se representa por\n--    N 9 (N 3 (H 2) (H 4)) (H 7) \n-- ---------------------------------------------------------------------\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n             deriving (Show, Eq)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    nHojas :: Arbol a -> Int\n-- tal que (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3\n-- ---------------------------------------------------------------------\n\nnHojas :: Arbol a -> Int\nnHojas (H _)     = 1\nnHojas (N x i d) = nHojas i + nHojas d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir la funci\u00f3n\n--    nNodos :: Arbol a -> Int\n-- tal que (nNodos x) es el n\u00famero de nodos del \u00e1rbol x. Por ejemplo,\n--    nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2\n-- ---------------------------------------------------------------------\n\nnNodos :: Arbol a -> Int\nnNodos (H _)     = 0\nnNodos (N x i d) = 1 + nNodos i + nNodos d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Comprobar con QuickCheck que en todo \u00e1rbol binario el\n-- n\u00famero de sus hojas es igual al n\u00famero de sus nodos m\u00e1s uno.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_nHojas :: Arbol Int -> Bool\nprop_nHojas x =\n    nHojas x == nNodos x + 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nHojas\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Definir la funci\u00f3n\n--    profundidad :: Arbol a -> Int\n-- tal que (profundidad x) es la profundidad del \u00e1rbol x. Por ejemplo,\n--    profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2\n--    profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3\n--    profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2\n-- ---------------------------------------------------------------------\n\nprofundidad :: Arbol a -> Int\nprofundidad (H _)     = 0\nprofundidad (N x i d) = 1 + max (profundidad i) (profundidad d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Comprobar con QuickCheck que para todo \u00e1rbol biario\n-- x, se tiene que\n--    nNodos x <= 2^(profundidad x) - 1\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_nNodosProfundidad :: Arbol Int -> Bool\nprop_nNodosProfundidad x =\n   nNodos x <= 2^(profundidad x) - 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nNodosProfundidad\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Definir la funci\u00f3n\n--    preorden :: Arbol a -> [a]\n-- tal que (preorden x) es la lista correspondiente al recorrido\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\n-- sub\u00e1rbol derecho. Por ejemplo,\n--    preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n-- ---------------------------------------------------------------------\n\npreorden :: Arbol a -> [a]\npreorden (H x)     = [x]\npreorden (N x i d) = x : (preorden i ++ preorden d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Comprobar con QuickCheck que la longitud de la lista\n-- obtenida recorriendo un \u00e1rbol en sentido preorden es igual al n\u00famero\n-- de nodos del \u00e1rbol m\u00e1s el n\u00famero de hojas.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_length_preorden :: Arbol Int -> Bool\nprop_length_preorden x =\n   length (preorden x) == nNodos x + nHojas x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_length_preorden\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Definir la funci\u00f3n\n--    postorden :: Arbol a -> [a]\n-- tal que (postorden x) es la lista correspondiente al recorrido\n-- postorden del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol\n-- izquierdo, a continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz\n-- del \u00e1rbol. Por ejemplo,\n--    postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]\n-- ---------------------------------------------------------------------\n\npostorden :: Arbol a -> [a]\npostorden (H x)     = [x]\npostorden (N x i d) = postorden i ++ postorden d ++ [x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.4. Definir, usando un acumulador, la funci\u00f3n\n--    preordenIt :: Arbol a -> [a]\n-- tal que (preordenIt x) es la lista correspondiente al recorrido\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\n-- sub\u00e1rbol derecho. Por ejemplo,\n--    preordenIt (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n-- \n-- Nota: No usar (++) en la definici\u00f3n\n-- ---------------------------------------------------------------------\n\npreordenIt :: Arbol a -> [a]\npreordenIt x = preordenItAux x []\n    where preordenItAux (H x) xs     = x:xs\n          preordenItAux (N x i d) xs = \n              x : preordenItAux i (preordenItAux d xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.5. Comprobar con QuickCheck que preordenIt es equivalente\n-- a preorden. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_preordenIt :: Arbol Int -> Bool\nprop_preordenIt x =\n    preordenIt x == preorden x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_preordenIt\n--    OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la tercera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los primeros ejercicios de la relaci\u00f3n 8 sobre \u00e1rboles binarios definidos como tipo de dato algebraico. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/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":[265],"tags":[270,316],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5843"}],"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=5843"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5843\/revisions"}],"predecessor-version":[{"id":5844,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5843\/revisions\/5844"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}