Algoritmos y Estructuras de Datos (VJ1215)

void Conjunto::insertar(int unDato) {
   Nodo * n = raiz;
   while (n != nullptr) {
      if (n->dato == unDato)
	 return;
      else if (n->dato > unDato)
	 n = n->izquierdo;
      else
	 n = n->derecho;
   }
   n = new Nodo(unDato);
   laTalla++;
}
	

Esta solución es incorrecta, porque al hacer n = new Nodo(unDato) la dirección del nuevo nodo no queda almacenada en el atributo derecho ni en el atributo izquierdo de ningún otro nodo, ni en raiz cuando el árbol estaba vacío. Ese bucle solo sirve para no insertar el dato si está duplicado. Falta enlazar el nuevo nodo en el árbol.

Si eres de los que piensan que n = new Nodo(unDato) sí que puede cambiar raiz o el atributo izquierdo o derecho de un nodo porque antes se ha hecho n = raiz, n = n->izquierdo o n = n->derecho, haz el mismo razonamiento con variables enteras:

   int a = 3, n = a;
   n = 7;
	

¿Estamos metiendo 7 en a porque antes hemos hecho n = a? Evidentemente no. Pues lo mismo pasa cuando n es un puntero.

El mismo tipo de error se da en esta otra versión, en la que solamente se ha resuelto el problema cuando hay que modificar raiz:

void Conjunto::insertar(int unDato) {
   if (raiz == nullptr) {
      raiz = new Nodo(unDato);
      laTalla++;
   } else {
      Nodo * n = raiz;
      while (n != nullptr) {
	 if (unDato > n->dato) {
	    n = n->derecho;
	 }
	 else if (unDato < n->dato) {
	    n = n->izquierdo;
	 } else
	    return;
      }
      n = new Nodo(unDato);
      laTalla++;
   }
}
	

Si tu solución es así, una vez entendido por qué no funciona intenta corregirla antes de seguir leyendo.

void Conjunto::insertar(int unDato) {

   if (raiz == nullptr) {
      raiz = new Nodo(unDato);
      laTalla++;
   } else {
      Nodo * actual = raiz;
      Nodo * anterior;
      while (actual != nullptr) {
	 anterior = actual;
	 if (unDato < actual->dato)
	    actual = actual->izquierdo;
	 else if (unDato > actual->dato)
	    actual = actual->derecho;
	 else
	    return; // No insertamos duplicados
      }
      if (unDato < anterior->dato)
	 anterior->izquierdo = new Nodo(unDato);
      else
	 anterior->derecho = new Nodo(unDato);
      laTalla++:
   }
}  
	

Otro ejemplo de error sería que, por ejemplo en una solución como esta, faltase tratar el caso en que el nuevo nodo debe ser la raíz.

void Conjunto::insertar(int unDato) {

   if (raiz == nullptr) {
      raiz = new Nodo(unDato);
      laTalla++;
   } else {
      Nodo * actual = raiz;
      bool fin = false; 
      while (! fin)
	 if (unDato < actual->dato)
	    if (actual->izquierdo != nullptr)
	       actual = actual->izquierdo;
	    else {
	       actual->izquierdo =  new Nodo(unDato);
	       laTalla++;
	       fin = true;
	    }
	 else if (unDato > actual->dato)
	    if (actual->derecho != nullptr)
	       actual = actual->derecho;
	    else {
	       actual->derecho =  new Nodo(unDato);
	       laTalla++;
	       fin = true;
	    }
	 else
	    fin = true; // No insertamos duplicados
   }
}  
	

También podemos separar en un método auxiliar lo que en la solución 2 se hace igual en tres casos: crear el nuevo nodo e incrementar la talla. Inténtalo y luego mira la solución siguiente.

void Conjunto::insertar(int unDato) {
   if (raiz == nullptr)
      insertar(unDato, raiz);
   else {
      Nodo * actual = raiz;
      bool fin = false; 
      while (! fin)
	 if (unDato < actual->dato)
	    if (actual->izquierdo != nullptr)
	       actual = actual->izquierdo;
	    else {
	       insertar(unDato, actual->izquierdo);
	       fin = true;
	    }
	 else if (unDato > actual->dato)
	    if (actual->derecho != nullptr)
	       actual = actual->derecho;
	    else {
	       insertar(unDato, actual->derecho);
	       fin = true;
	    }
	 else
	    fin = true; // No insertamos duplicados
   }
}  

void Conjunto::insertar(int unDato, Nodo * & n) {
   n = new Nodo(unDato);
   laTalla++;
}
	

Observa que n se pasa por referencia para modificarlo.

void Conjunto::insertar(int unDato) {
   insertar(unDato, raiz);
}

void Conjunto::insertar(int unDato, Nodo * & n) {
   if (n == nullptr) {
      n = new Nodo(unDato);
      laTalla++;
   } else {
      bool fin = false; 
      while (! fin)
	 if (unDato < n->dato)
	    if (n->izquierdo != nullptr)
	       n = n->izquierdo;
	    else {
	       n->izquierdo =  new Nodo(unDato);
	       laTalla++;
	       fin = true;
	    }
	 else if (unDato > n->dato)
	    if (n->derecho != nullptr)
	       n = n->derecho;
	    else {
	       n->derecho =  new Nodo(unDato);
	       laTalla++;
	       fin = true;
	    }
	 else
	    fin = true; // No insertamos duplicados
   }
}  
	

Esta solución es incorrecta, porque al hacer n = n->izquierdo o n = n->derecho estamos modificando la raíz del árbol que hemos pasado por referencia.

Observa que para resolver eso no basta quitar el & para que n no se pase por referencia: de ese modo la asignación n = new Nodo(unDato) no dejaría la dirección del nuevo nodo en el atributo raiz. Hay que hacer más cambios. Una forma de corregir este código es convertirlo en el de la solución 2, no estamos ganando nada con esta forma de dividir el código en dos métodos.