{"id":7754,"date":"2022-12-29T06:00:11","date_gmt":"2022-12-29T04:00:11","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7754"},"modified":"2022-12-26T14:34:54","modified_gmt":"2022-12-26T12:34:54","slug":"29-dic-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/29-dic-22\/","title":{"rendered":"\u00c1rboles con igual estructura"},"content":{"rendered":"

Los \u00e1rboles binarios con valores en las hojas y en los nodos se definen por<\/p>\n

\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n
Por ejemplo, los \u00e1rboles<\/p>\n
\n        5              8             5           5\n       \/ \\            \/ \\           \/ \\         \/ \\\n      \/   \\          \/   \\         \/   \\       \/   \\\n     9     7        9     3       9     2     4     7\n    \/ \\   \/ \\      \/ \\   \/ \\     \/ \\               \/ \\\n   1   4 6   8    1   4 6   2   1   4             6   2\n<\/pre>\n
se pueden representar por<\/p>\n
\n   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int\n   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))\n   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))\n   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)\n   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   igualEstructura :: Arbol -> Arbol -> Bool\n<\/pre>\n
tal que igualEstructura a1 a2<\/code> se verifica si los \u00e1rboles a1<\/code> y a2<\/code> tienen la misma estructura. Por ejemplo,<\/p>\n
\n   igualEstructura ej3arbol1 ej3arbol2 == True\n   igualEstructura ej3arbol1 ej3arbol3 == False\n   igualEstructura ej3arbol1 ej3arbol4 == 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 = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int\nej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))\nej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))\nej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)\nej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))\n\nigualEstructura :: Arbol a -> Arbol a -> Bool\nigualEstructura (H _) (H _)             = True\nigualEstructura (N _ i1 d1) (N _ i2 d2) =\n  igualEstructura i1 i2 &&\n  igualEstructura d1 d2\nigualEstructura _ _                       = False\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    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\nej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))\nej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))\nej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))\nej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))\n\ndef igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:\n    match (a, b):\n        case (H(_), H(_)):\n            return True\n        case (N(_, i1, d1), N(_, i2, d2)):\n            return igualEstructura(i1, i2) and igualEstructura(d1, d2)\n        case (_, _):\n            return False\n    assert False\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Los \u00e1rboles binarios con valores en las hojas y en los nodos se definen por data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show Por ejemplo, los \u00e1rboles 5 8 5 5 \/ \\ \/ \\ \/ \\ \/ \\ \/ \\ \/ \\ \/ \\ \/ \\ 9…<\/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\/7754"}],"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=7754"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7754\/revisions"}],"predecessor-version":[{"id":7755,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7754\/revisions\/7755"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}