Curso 2024/2025
bool Conjunto::arbolesIguales(const Conjunto & otroConjunto) const { return arbolesIguales(raiz, otroConjunto.raiz); } bool Conjunto::arbolesIguales(Nodo * n1, Nodo * n2) const { if (n1 == nullptr && n2 == nullptr) return true; if (n1 == nullptr || n2 == nullptr) return false; if (n1->dato != n2->dato) return false; return arbolesIguales(n1->izquierdo, n2->izquierdo) && arbolesIguales(n1->derecho, n2->derecho); }
Dicho de otro modo:
bool Conjunto::arbolesIguales(const Conjunto & otroConjunto) const { return arbolesIguales(raiz, otroConjunto.raiz); } bool Conjunto::arbolesIguales(Nodo * n1, Nodo * n2) const { return (n1 == nullptr && n2 == nullptr) || (n1 != nullptr && n2 != nullptr && n1->dato == n2->dato && arbolesIguales(n1->izquierdo, n2->izquierdo) && arbolesIguales(n1->derecho, n2->derecho)); }
El coste temporal es O(n), siendo n la cantidad de nodos del árbol que menos nodos tenga.
También sería razonable, si tuviéramos un atributo con la talla (cantidad de nodos), empezar devolviendo falso si las dos tallas difieren:
bool Conjunto::arbolesIguales(const Conjunto & otroConjunto) const { return laTalla == otroConjunto.laTalla && arbolesIguales(raiz, otroConjunto.raiz); }
Con eso ganaríamos eficiencia cuando las tallas son diferentes. No obstante, las soluciones anteriores funcionarían correctamente también en ese caso.