Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 2 del tema 3

El coste temporal de las siguientes soluciones es O(n), siendo n la talla del conjunto, debido a que se hacen O(n) llamadas recursivas y el coste propio de cada llamada es O(1).

Solución 1

int Conjunto::sumar() const {
   return sumar(raiz);
}

int Conjunto::sumar(Nodo * n) const {
   if (n == nullptr)
      return 0;
   return n->dato + sumar(n->izquierdo) + sumar(n->derecho);
}

Observa cómo la solución anterior, a diferencia de la que se muestra a continuación, trata en un solo sitio los casos en que no hay subárbol izquierdo, no hay subárbol derecho o el árbol está vacío.

Solución 2

int Conjunto::sumar() const {
   if (raiz == nullptr)
      return 0;
   return sumar(raiz);
}

int Conjunto::sumar(Nodo * n) const {

   int resultado;
   
   if (n->izquierdo != nullptr && n->derecho != nullptr)
      resultado = n->dato + sumar(n->izquierdo) + sumar(n->derecho);
   else if (n->izquierdo != nullptr)
      resultado = n->dato + sumar(n->izquierdo);
   else if(n->derecho != nullptr)
      resultado = n->dato + sumar(n->derecho);
   else
      resultado = n->dato;
   
   return resultado;
}

Compara esta solución con la solución 1.

Solución 3

int Conjunto::sumar() const {
   int resultado = 0;
   sumar(raiz, resultado);
   return resultado;
}

void Conjunto::sumar(Nodo * n, int & suma) const {
   if(n == nullptr)
      return;
   suma += n->dato;
   sumar(n->izquierdo, suma);
   sumar(n->derecho, suma);
}