Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2022/2023

Solución del ejercicio 1.h del tema 3

Compara las dos soluciones siguientes y elige la que prefieras.

El orden en que se liberan los nodos en estas soluciones es el de un recorrido en postorden: se elimina cada nodo después de haber eliminado los de su subárbol izquierdo y los de su subárbol derecho.

Observa que no es necesario pasar n por referencia. La instrucción delete n libera la memoria que indica n, pero no modifica el valor de n.

¿Por qué no es necesario poner nullptr en los atributos de cada nodo, pero sí que es necesario dejar nullptr en la raíz? Recuerda.

Solución 1 

void Conjunto::vaciar() {
   vaciar(raiz);
   raiz = nullptr;
   laTalla = 0;
}

void Conjunto::vaciar(Nodo * n) {
   if (n != nullptr) {
      vaciar(n->izquierdo);
      vaciar(n->derecho);
      delete n;
   }
}

Solución 2 

void Conjunto::vaciar() {
   if (raiz != nullptr) {
      vaciar(raiz);
      raiz = nullptr;
      laTalla = 0;
   }
}

void Conjunto::vaciar(Nodo * n) {
   if (n->izquierdo != nullptr)
      vaciar(n->izquierdo);
   if (n->derecho != nullptr)
      vaciar(n->derecho);
   delete n;
}

Ejemplos de errores 

void Conjunto::vaciar() {
   return vaciar(raiz);
}

void Conjunto::vaciar(Nodo * & n) {
   if (n->izquierdo != nullptr) {
      vaciar(n->izquierdo);
      delete n; 
   } else if (n->derecho != nullptr) {
      vaciar(n->derecho);
      delete n:
   }
}

Aquí hay 4 errores:

  1. Se utiliza incorrectamente return.

  2. El segundo método falla si raiz vale nullptr.

  3. Sobra else (y al corregir eso no hay que hacer delete dos veces).

  4. Falta que, tras vaciar el conjunto, quede 0 en la talla y nullptr en la raíz.

Por otra parte, aunque no sea un error, no es necesario pasar n por referencia.