{"id":6877,"date":"2022-04-06T06:00:48","date_gmt":"2022-04-06T04:00:48","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6877"},"modified":"2022-04-13T11:25:57","modified_gmt":"2022-04-13T09:25:57","slug":"enumeracion-de-arboles-binarios","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/enumeracion-de-arboles-binarios\/","title":{"rendered":"Enumeraci\u00f3n de \u00e1rboles binarios"},"content":{"rendered":"<p>Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N (Arbol a) a (Arbol a)\n      deriving Show\n<\/pre>\n<p>Por ejemplo, el \u00e1rbol<\/p>\n<pre lang=\"text\">\n        \"B\"\n        \/ \\\n       \/   \\\n      \/     \\\n    \"B\"     \"A\"\n    \/ \\     \/ \\\n  \"A\" \"B\" \"C\" \"C\"\n<\/pre>\n<p>se puede definir por<\/p>\n<pre lang=\"text\">\n   ej1 :: Arbol String\n   ej1 = N (N (H \"A\") \"B\" (H \"B\")) \"B\" (N (H \"C\") \"A\" (H \"C\"))\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   enumeraArbol :: Arbol t -> Arbol Int\n<\/pre>\n<p>tal que (enumeraArbol a) es el \u00e1rbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la ra\u00edz. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> enumeraArbol ej1\n   N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))\n<\/pre>\n<p>Gr\u00e1ficamente,<\/p>\n<pre lang=\"text\">\n         3\n        \/ \\\n       \/   \\\n      \/     \\\n     1       5\n    \/ \\     \/ \\\n   0   2   4   6\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, quickCheck, sized)\nimport Control.Monad.State (State, evalState, get, put)\n\ndata Arbol a = H a\n             | N (Arbol a) a (Arbol a)\n  deriving (Show, Eq)\n\nej1 :: Arbol String\nej1 = N (N (H \"A\") \"B\" (H \"B\")) \"B\" (N (H \"C\") \"A\" (H \"C\"))\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol1 :: Arbol t -> Arbol Int\nenumeraArbol1 a = fst (aux a 0)\n  where aux :: Arbol t -> Int -> (Arbol Int, Int)\n        aux (H _) n     = (H n, n+1)\n        aux (N i _ d) n = (N i' n1 d', n2)\n          where (i', n1) = aux i n\n                (d', n2) = aux d (n1+1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol2 :: Arbol t -> Arbol Int\nenumeraArbol2 a = evalState (aux a) 0\n  where aux :: Arbol t -> State Int (Arbol Int)\n        aux (H _)     = H <$> contador\n        aux (N i _ d) = do\n          i' <- aux i\n          n1 <- contador\n          d' <- aux d\n          return (N i' n1 d')\n\ncontador :: State Int Int\ncontador = do\n  n <- get\n  put (n+1)\n  return n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol3 :: Arbol t -> Arbol Int\nenumeraArbol3 a = evalState (aux a) 0\n  where aux :: Arbol t -> State Int (Arbol Int)\n        aux (H _)     = H <$> contador\n        aux (N i _ d) = N <$> aux i <*> contador <*> aux d\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- (arbolArbitrario n) genera un \u00e1rbol aleatorio de orden n. Por\n-- ejemplo,\n--    \u03bb> generate (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N (N (H 19) 0 (H (-27))) 21 (N (H 2) 17 (H 26))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario n\n  | n <= 0    = H <$> arbitrary\n  | otherwise = N <$> subarbol <*> arbitrary <*> subarbol\n  where subarbol = arbolArbitrario (n `div` 2)\n\n-- Arbol es una subclase de Arbitrary.\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_enumeraArbol :: Arbol Int -> Bool\nprop_enumeraArbol a =\n  all (== enumeraArbol1 a)\n      [enumeraArbol2 a,\n       enumeraArbol3 a]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_enumeraArbol\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Enumera_arbol.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/JbLEKUZ2E2M\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido por data Arbol a = H a | N (Arbol a) a (Arbol a) deriving Show Por ejemplo, el \u00e1rbol \u00abB\u00bb \/ \\ \/ \\ \/ \\ \u00abB\u00bb \u00abA\u00bb \/ \\ \/ \\ \u00abA\u00bb \u00abB\u00bb \u00abC\u00bb \u00abC\u00bb se puede definir por ej1 :: Arbol&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[2],"tags":[41,483,269,528,529,80,530,15,11,541,6,371,518,146,133],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6877"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6877"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6877\/revisions"}],"predecessor-version":[{"id":6907,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6877\/revisions\/6907"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6877"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6877"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6877"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}