{"id":2497,"date":"2016-05-27T06:00:27","date_gmt":"2016-05-27T04:00:27","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2497"},"modified":"2016-05-27T22:21:25","modified_gmt":"2016-05-27T20:21:25","slug":"construccion-del-arbol-a-partir-de-los-recorridos-preorden-e-inorden","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/construccion-del-arbol-a-partir-de-los-recorridos-preorden-e-inorden\/","title":{"rendered":"Construcci\u00f3n del \u00e1rbol a partir de los recorridos preorden e inorden"},"content":{"rendered":"<p>Los \u00e1rboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n                deriving (Show, Eq)\n<\/pre>\n<p>Por ejemplo, el \u00e1rbol<\/p>\n<pre lang=\"text\">\n        9 \n       \/ \\\n      \/   \\\n     3     7\n    \/ \\  \n   2   4 \n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7) \n<\/pre>\n<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   preorden :: Arbol a -> [a]\n   inorden  :: Arbol a -> [a]\n   arboles  :: Eq a => [a] -> [a] -> [Arbol a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(preorden x) es la lista correspondiente al recorrido preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el sub\u00e1rbol derecho. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n<\/pre>\n<ul>\n<li>(inorden x) es la lista correspondiente al recorrido inorden del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol izquierdo, a continuaci\u00f3n visita la ra\u00edz del \u00e1rbol y, finalmente, recorre el sub\u00e1rbol derecho. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     inorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,3,4,9,7]  \n<\/pre>\n<ul>\n<li>(arboles xs ys) es la lista de los \u00e1rboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n      \u03bb> arboles [9,3,2,4,7] [2,3,4,9,7]\n      [N 9 (N 3 (H 2) (H 4)) (H 7)]\n      \u03bb> arboles [9,3,2,4,7] [2,4,3,9,7]\n      []\n      \u03bb> arboles [1,1,1,2,3] [1,1,2,1,3]\n      [N 1 (H 1) (N 1 (H 2) (H 3)),\n       N 1 (N 1 (H 1) (H 2)) (H 3)]\n      \u03bb> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))\n      \u03bb> arboles (preorden x) (inorden x)\n      [N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),\n       N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),\n       N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),\n       N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]\n<\/pre>\n<p>Comprobar con QuickCheck, que para todo \u00e1rbol x se verifican las siguientes propiedades<\/p>\n<pre lang=\"text\">\n    prop_arboles1 :: Arbol Int -> Bool\n    prop_arboles1 x =\n        x `elem` arboles (preorden x) (inorden x)\n    \n    prop_arboles2 :: Arbol Int -> Bool\n    prop_arboles2 x =\n        and [preorden a == xs && inorden a == ys | a <- as] \n        where xs = preorden x\n              ys = inorden x\n              as = arboles xs ys\n<\/pre>\n<p>Nota: Para la comprobaci\u00f3n, se usa el siguiente generador<\/p>\n<pre lang=\"text\">\n   import Control.Monad \n   \n   instance Arbitrary a => Arbitrary (Arbol a) where\n     arbitrary = sized arbol\n       where\n         arbol 0       = liftM H arbitrary \n         arbol n | n>0 = oneof [liftM H arbitrary,\n                                liftM3 N arbitrary subarbol subarbol]\n                         where subarbol = arbol (div n 2)\n<\/pre>\n<h4>Soluciones<\/h4>\n<p>[schedule expon='2016-06-02' expat=\"06:00\"]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 02 de junio.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\"haskell\"&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on='2016-06-02' at=\"06:00\"]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.List (elemIndex, elemIndices)\r\nimport Data.Maybe (isJust, fromJust)\r\nimport Test.QuickCheck\r\nimport Control.Monad \r\n\r\ndata Arbol a = H a\r\n             | N a (Arbol a) (Arbol a)\r\n             deriving (Show, Eq)\r\n\r\npreorden :: Arbol a -> [a]\r\npreorden (H x)     = [x]\r\npreorden (N x i d) = x : (preorden i ++ preorden d)\r\n\r\ninorden :: Arbol a -> [a]\r\ninorden (H x)     = [x]\r\ninorden (N x i d) = inorden i ++ (x : inorden d)\r\n\r\narboles :: Eq a => [a] -> [a] -> [Arbol a]\r\narboles [] _      = []\r\narboles [x] ys | ys == [x] = [H x]\r\n               | otherwise = []\r\narboles (x:xs) ys =\r\n    [N x i d | k <- elemIndices x ys \r\n             , let (ys1,_:ys2) = splitAt k ys\r\n             , let (xs1,xs2)   = splitAt k xs\r\n             , i <- arboles xs1 ys1\r\n             , d <- arboles xs2 ys2]\r\n\r\nprop_arboles1 :: Arbol Int -> Bool\r\nprop_arboles1 x =\r\n    x `elem` arboles (preorden x) (inorden x)\r\n\r\nprop_arboles2 :: Arbol Int -> Bool\r\nprop_arboles2 x =\r\n    and [preorden a == xs && inorden a == ys | a <- as] \r\n    where xs = preorden x\r\n          ys = inorden x\r\n          as = arboles xs ys\r\n\r\ninstance Arbitrary a => Arbitrary (Arbol a) where\r\n  arbitrary = sized arbol\r\n    where\r\n      arbol 0       = liftM H arbitrary \r\n      arbol n | n>0 = oneof [liftM H arbitrary,\r\n                             liftM3 N arbitrary subarbol subarbol]\r\n                      where subarbol = arbol (div n 2)\r\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Los \u00e1rboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) Por ejemplo, el \u00e1rbol 9 \/ \\ \/ \\ 3 7 \/ \\ 2 4 se representa por N 9&#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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2497"}],"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=2497"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2497\/revisions"}],"predecessor-version":[{"id":2502,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2497\/revisions\/2502"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2497"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2497"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2497"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}