{"id":4366,"date":"2018-12-03T06:00:06","date_gmt":"2018-12-03T04:00:06","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4366"},"modified":"2019-01-19T12:06:24","modified_gmt":"2019-01-19T10:06:24","slug":"numeracion-de-los-arboles-binarios-completos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeracion-de-los-arboles-binarios-completos\/","title":{"rendered":"Numeraci\u00f3n de los \u00e1rboles binarios completos"},"content":{"rendered":"<p>Un <a href=\"http:\/\/bit.ly\/2DUr53g\">\u00e1rbol binario completo<\/a> es un \u00e1rbol binario que tiene todos los nodos posibles hasta el pen\u00faltimo nivel, y donde los elementos del \u00faltimo nivel est\u00e1n colocados de izquierda a derecha sin dejar huecos entre ellos.<\/p>\n<p>La numeraci\u00f3n de los \u00e1rboles binarios completos se realiza a partir de la ra\u00edz, recorriendo los niveles de izquierda a derecha. Por ejemplo,<\/p>\n<pre lang=\"text\">  \n                  1\n                 \/  \\\n                \/    \\\n               \/      \\\n              2        3\n             \/ \\      \/ \\\n            4   5    6   7\n           \/ \\    \n          8   9 \n<\/pre>\n<p>Los \u00e1rboles binarios se puede representar mediante el siguiente tipo<\/p>\n<pre lang=\"text\">  \n   data Arbol = H\n              | N Int Arbol Arbol\n     deriving (Show, Eq)\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">  \n    arbolBinarioCompleto :: Int -> Arbol\n<\/pre>\n<p>tal que (arbolBinarioCompleto n) es el \u00e1rbol binario completo con n<br \/>\nnodos. Por ejemplo,<\/p>\n<pre lang=\"text\">  \n   \u03bb> arbolBinarioCompleto 4\n   N 1 (N 2 (N 4 H H) H) (N 3 H H)\n   \u03bb> arbolBinarioCompleto 9\n   N 1\n     (N 2\n        (N 4\n           (N 8 H H)\n           (N 9 H H))\n        (N 5 H H))\n     (N 3\n        (N 6 H H)\n        (N 7 H H))\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\ndata Arbol = H\n           | N Int Arbol Arbol\n  deriving (Eq, Show)\n\narbolBinarioCompleto :: Int -> Arbol\narbolBinarioCompleto n = aux 1\n  where aux i | i <= n    = N i (aux (2*i)) (aux (2*i+1))\n              | otherwise = H\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n- Ya se oyen palabras viejas.<br \/>\n- Pues aguzad las orejas.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Un \u00e1rbol binario completo es un \u00e1rbol binario que tiene todos los nodos posibles hasta el pen\u00faltimo nivel, y donde los elementos del \u00faltimo nivel est\u00e1n colocados de izquierda a derecha sin dejar huecos entre ellos. La numeraci\u00f3n de los \u00e1rboles binarios completos se realiza a partir de la ra\u00edz, recorriendo los niveles de izquierda&#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":[4],"tags":[269,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4366"}],"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=4366"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4366\/revisions"}],"predecessor-version":[{"id":4586,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4366\/revisions\/4586"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4366"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4366"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4366"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}