{"id":7730,"date":"2022-12-19T06:00:21","date_gmt":"2022-12-19T04:00:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7730"},"modified":"2022-12-18T20:31:22","modified_gmt":"2022-12-18T18:31:22","slug":"19-dic-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-dic-22\/","title":{"rendered":"Recorrido de \u00e1rboles binarios"},"content":{"rendered":"<p>El \u00e1rbol binario<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     3     7\n    \/ \\\n   2   4\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>El tipo de los \u00e1rboles binarios se puede definir por<\/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>Definir las funciones<\/p>\n<pre lang=\"text\">\n   preorden  :: Arbol a -> [a]\n   postorden :: Arbol a -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>preorden<\/code> es la lista correspondiente al recorrido preorden del \u00e1rbol <code>x<\/code>; 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><code>postorden x<\/code> es la lista correspondiente al recorrido postorden del \u00e1rbol <code>x<\/code>; es decir, primero recorre el sub\u00e1rbol izquierdo, a continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz del \u00e1rbol. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]\n<\/pre>\n<p>Comprobar con QuickCheck que la longitud de la lista obtenida recorriendo un \u00e1rbol en cualquiera de los sentidos es igual al n\u00famero de nodos del \u00e1rbol m\u00e1s el n\u00famero de hojas.<br \/>\n<b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\npreorden :: Arbol a -> [a]\npreorden (H x)     = [x]\npreorden (N x i d) = x : preorden i ++ preorden d\n\npostorden :: Arbol a -> [a]\npostorden (H x)     = [x]\npostorden (N x i d) = postorden i ++ postorden d ++ [x]\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de altura n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N 0 (H 0) (H 0)\n--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)\n--    N 3 (H 1) (H 2)\n--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))\n--    H 7\n--    N (-8) (H (-8)) (H 9)\n--    H 2\n--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))\n--    H (-3)\n--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)\n--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario 0 = H <$> arbitrary\narbolArbitrario n =\n  oneof [H <$> arbitrary,\n         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]\n\n-- Arbol es subclase de Arbitrary\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_longitud_recorrido :: Arbol Int -> Bool\nprop_longitud_recorrido x =\n   length (preorden x)  == n &&\n   length (postorden x) == n\n   where n = nNodos x + nHojas x\n\n-- (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\nnNodos :: Arbol a -> Int\nnNodos (H _)     = 0\nnNodos (N _ i d) = 1 + nNodos i + nNodos d\n\n-- (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\nnHojas :: Arbol a -> Int\nnHojas (H _)     = 1\nnHojas (N _ i d) = nHojas i + nHojas d\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_longitud_recorrido\n--    OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\nfrom random import choice, randint\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    x: A\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef preorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return [x] + preorden(i) + preorden(d)\n    assert False\n\ndef postorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return postorden(i) + postorden(d) + [x]\n    assert False\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n#    >>> arbolArbitrario(4)\n#    N(x=2, i=H(x=1), d=H(x=9))\n#    >>> arbolArbitrario(4)\n#    H(x=10)\n#    >>> arbolArbitrario(4)\n#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))\ndef arbolArbitrario(n: int) -> Arbol[int]:\n    if n <= 1:\n        return H(randint(0, 10))\n    m = n \/\/ 2\n    return choice([H(randint(0, 10)),\n                   N(randint(0, 10),\n                     arbolArbitrario(m),\n                     arbolArbitrario(m))])\n\n# 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\ndef nNodos(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 0\n        case N(_, i, d):\n            return 1 + nNodos(i) + nNodos(d)\n    assert False\n\n# (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\ndef nHojas(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 1\n        case N(_, i, d):\n            return nHojas(i) + nHojas(d)\n    assert False\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=10))\ndef test_recorrido(n: int) -> None:\n    a = arbolArbitrario(n)\n    m = nNodos(a) + nHojas(a)\n    assert len(preorden(a)) == m\n    assert len(postorden(a)) == m\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q recorrido_de_arboles_binarios.py\n#    1 passed in 0.16s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El \u00e1rbol binario 9 \/ \\ \/ \\ 3 7 \/ \\ 2 4 se puede representar por N 9 (N 3 (H 2) (H 4)) (H 7) El tipo de los \u00e1rboles binarios se puede definir por data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) Definir&#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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7730"}],"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=7730"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7730\/revisions"}],"predecessor-version":[{"id":7732,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7730\/revisions\/7732"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}