=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2023/2024
17 de noviembre de 2023
Ejercicio 3.b
Borrador
=================================================================


Costes
======

Coste temporal en el peor caso: O(n)

Coste espacial en el peor caso, si la solucion usa una cola: O(n), porque de la cola
cuando salen los nodos de un nivel entran los nodos del nivel siguiente, y en el nivel
mas profundo podemos llegar a tener O(n/2) = O(n) nodos si el arbol esta equilibrado.

Coste espacial en el peor caso, si la solucion usa una pila: O(n), porque la cantidad
maxima de nodos en la pila viene dada por la altura del arbol, que puede llegar a ser O(n)
cuando todos los nodos, excepto uno, tienen un solo hijo.


Solucion 1
==========

void Conjunto::eliminarHojas() {
   if (raiz != nullptr)
      if (raiz->izquierdo == nullptr && raiz->derecho == nullptr) {
	 delete raiz;
	 raiz = nullptr;
      } else {
	 queue <Nodo *> cola; // Tambien sirve stack en este ejercicio
	 cola.push(raiz);
	 while (! cola.empty()) {
	    Nodo * n = cola.front();
	    cola.pop();
	    Nodo * izquierdo = n->izquierdo;
	    Nodo * derecho = n->derecho;
	    if (izquierdo != nullptr)
	       if (izquierdo->izquierdo == nullptr && izquierdo->derecho == nullptr) {
		  delete izquierdo;
		  n->izquierdo = nullptr;
	       } else
		  cola.push(izquierdo);
	    if (derecho != nullptr) 
	       if (derecho->izquierdo == nullptr && derecho->derecho == nullptr) {
		  delete derecho;
		  n->derecho = nullptr;
	       } else
		  cola.push(derecho);
	 }
      }
}


Solucion 2
==========

bool Conjunto::esHoja(Nodo * n) const {
   return n->izquierdo == nullptr && n->derecho == nullptr;
}

void Conjunto::eliminarHojas() {
   if (raiz == nullptr)
      return;
   if (esHoja(raiz)) {
      delete raiz;
      raiz = nullptr;
   } else {
      queue<Nodo *> cola;  // Tambien sirve stack en este ejercicio
      cola.push(raiz);
      while (! cola.empty()) {
	 Nodo * n = cola.front();
	 cola.pop();
	 if (n->izquierdo != nullptr)
	    if (esHoja(n->izquierdo)) {
	       delete n->izquierdo;
	       n->izquierdo = nullptr;
	    } else
	       cola.push(n->izquierdo);
	 if (n->derecho != nullptr)
	    if (esHoja(n->derecho)) {
	       delete n->derecho;
	       n->derecho = nullptr;
	    } else
	       cola.push(n->derecho);
      }
   }
}