Algoritmos y Estructuras de Datos (VJ1215)

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.