Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

Solución del ejercicio 1.b 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).

Su coste espacial es O(n) debido a que tenemos un árbol con n nodos, a lo que se suma el coste de la pila de llamadas recursivas que en el peor caso, si tuviéramos un árbol de altura n, también sería O(n).

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.

Ejemplo de error y solución 2

Piensa en qué caso puede fallar la siguiente solución. 

int Conjunto::sumar() const {
   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;
}

Solución

Falla si raiz vale nullptr. Eso se podría resolver así: 

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 que se ha proporcionado al principio.

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);
}