{"id":7752,"date":"2022-12-28T06:00:24","date_gmt":"2022-12-28T04:00:24","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7752"},"modified":"2022-12-26T12:36:07","modified_gmt":"2022-12-26T10:36:07","slug":"28-dic-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/28-dic-22\/","title":{"rendered":"\u00c1rboles con bordes iguales"},"content":{"rendered":"

Los \u00e1rboles binarios con valores en las hojas se pueden definir por<\/p>\n

\n   data Arbol a = H a\n                | N (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n
Por ejemplo, los \u00e1rboles<\/p>\n
\n   \u00e1rbol1          \u00e1rbol2       \u00e1rbol3     \u00e1rbol4\n      o              o           o           o\n     \/ \\            \/ \\         \/ \\         \/ \\\n    1   o          o   3       o   3       o   1\n       \/ \\        \/ \\         \/ \\         \/ \\\n      2   3      1   2       1   4       2   3\n<\/pre>\n
se representan por<\/p>\n
\n   arbol1, arbol2, arbol3, arbol4 :: Arbol Int\n   arbol1 = N (H 1) (N (H 2) (H 3))\n   arbol2 = N (N (H 1) (H 2)) (H 3)\n   arbol3 = N (N (H 1) (H 4)) (H 3)\n   arbol4 = N (N (H 2) (H 3)) (H 1)\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool\n<\/pre>\n
tal que igualBorde t1 t2<\/code> se verifica si los bordes de los \u00e1rboles t1<\/code> y t2<\/code> son iguales. Por ejemplo,<\/p>\n
\n   igualBorde arbol1 arbol2  ==  True\n   igualBorde arbol1 arbol3  ==  False\n   igualBorde arbol1 arbol4  ==  False\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\ndata Arbol a = N (Arbol a) (Arbol a)\n             | H a\n  deriving Show\n\narbol1, arbol2, arbol3, arbol4 :: Arbol Int\narbol1 = N (H 1) (N (H 2) (H 3))\narbol2 = N (N (H 1) (H 2)) (H 3)\narbol3 = N (N (H 1) (H 4)) (H 3)\narbol4 = N (N (H 2) (H 3)) (H 1)\n\nigualBorde :: Eq a => Arbol a -> Arbol a -> Bool\nigualBorde t1 t2 = borde t1 == borde t2\n\n-- (borde t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\n-- del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo,\n--    borde arbol4  ==  [2,3,1]\nborde :: Arbol a -> [a]\nborde (N i d) = borde i ++ borde d\nborde (H x)   = [x]\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom dataclasses import dataclass\nfrom typing import Generic, TypeVar\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    i: Arbol[A]\n    d: Arbol[A]\n\narbol1: Arbol[int] = N(H(1), N(H(2), H(3)))\narbol2: Arbol[int] = N(N(H(1), H(2)), H(3))\narbol3: Arbol[int] = N(N(H(1), H(4)), H(3))\narbol4: Arbol[int] = N(N(H(2), H(3)), H(1))\n\n# borde(t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\n# del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo,\n#    borde(arbol4)  ==  [2, 3, 1]\ndef borde(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(i, d):\n            return borde(i) + borde(d)\n    assert False\n\ndef igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool:\n    return borde(t1) == borde(t2)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Los \u00e1rboles binarios con valores en las hojas se pueden definir por data Arbol a = H a | N (Arbol a) (Arbol a) deriving Show Por ejemplo, los \u00e1rboles \u00e1rbol1 \u00e1rbol2 \u00e1rbol3 \u00e1rbol4 o o o o \/ \\ \/ \\ \/ \\ \/ \\ 1 o o 3 o 3 o 1 \/…<\/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\/7752"}],"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=7752"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7752\/revisions"}],"predecessor-version":[{"id":7753,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7752\/revisions\/7753"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7752"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7752"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7752"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}