{"id":2905,"date":"2017-02-10T06:00:17","date_gmt":"2017-02-10T04:00:17","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2905"},"modified":"2017-02-17T07:10:34","modified_gmt":"2017-02-17T05:10:34","slug":"caminos-en-un-arbol-binario-con-suma-dada","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/caminos-en-un-arbol-binario-con-suma-dada\/","title":{"rendered":"Caminos en un \u00e1rbol binario con suma dada"},"content":{"rendered":"<p>Los \u00e1rboles binarios se pueden representar con el de tipo de dato algebraico<\/p>\n<pre lang=\"text\">\n   data Arbol = H\n              | N Int Arbol Arbol\n     deriving Show\n<\/pre>\n<p>Por ejemplo, los \u00e1rboles<\/p>\n<pre lang=\"text\">\n       3                7                 1\n      \/ \\              \/ \\               \/  \\\n     2   4            5   8             \/    \\\n    \/ \\   \\          \/   \/ \\           \/      \\\n   1   7   5        6   4   9         3       -1\n                                     \/ \\     \/  \\\n                                    2   1   4    5                        \n                                       \/   \/ \\    \\                    \n                                      1   1   2    6    \n<\/pre>\n<p>se representan por<\/p>\n<pre lang=\"text\">\n   ej1, ej2, ej3 :: Arbol\n   ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))\n   ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))\n   ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))\n             (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   caminos     :: Arbol -> [[Int]]\n   caminosSuma :: Arbol -> Int -> [[Int]]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(caminos a) es la lista de los caminos entre dos nodos cualesquiera del \u00e1rbol a. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> caminos ej1\n     [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5],\n      [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]]\n     \u03bb> caminos ej2\n     [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9],\n      [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]]\n     \u03bb> length (caminos ej3)\n     33\n<\/pre>\n<ul>\n<li>(caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del \u00e1rbol a cuya suma es k. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> caminosSuma ej1 3\n     [[3],[2,1]]\n     \u03bb> caminosSuma ej3 3\n     [[3],[-1,4]]\n     \u03bb> caminosSuma ej3 4\n     [[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]]\n     \u03bb> caminosSuma ej3 5\n     [[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]]\n     \u03bb> caminosSuma ej3 6\n     [[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]]\n     \u03bb> caminosSuma ej3 7\n     []\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\ndata Arbol = H\n           | N Int Arbol Arbol\n  deriving Show\n\nej1, ej2, ej3 :: Arbol\nej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))\nej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))\nej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))\n          (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))\n  \ncaminos :: Arbol -> [[Int]]\ncaminos H           = []\ncaminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d\n\n-- (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la\n-- ra\u00edz de a hasta cualquiera de sus nodos. Por ejemplo.\n--    \u03bb> caminosDesdeRaiz ej1\n--    [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]\n--    \u03bb> caminosDesdeRaiz ej2\n--    [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]\ncaminosDesdeRaiz :: Arbol -> [[Int]]\ncaminosDesdeRaiz H = []\ncaminosDesdeRaiz (N x i d) =\n  [x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d]\n\ncaminosSuma :: Arbol -> Int -> [[Int]]\ncaminosSuma a k =\n  [ys | ys <- caminos a\n      , sum ys == k]\n<\/pre>\n<h4>Referencia<\/h4>\n<p>Basado en <a href=\"http:\/\/bit.ly\/2lbsaIn\">Print all k-sum paths in a binary tree<\/a> de GeeksforGeeks.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Los \u00e1rboles binarios se pueden representar con el de tipo de dato algebraico data Arbol = H | N Int Arbol Arbol deriving Show Por ejemplo, los \u00e1rboles 3 7 1 \/ \\ \/ \\ \/ \\ 2 4 5 8 \/ \\ \/ \\ \\ \/ \/ \\ \/ \\ 1 7 5 6&#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,8,6,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2905"}],"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=2905"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2905\/revisions"}],"predecessor-version":[{"id":2971,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2905\/revisions\/2971"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2905"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2905"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2905"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}