Algoritmos y Estructuras de Datos - VJ1215

Ejemplos de errores en el ejercicio 9.b del tema 3

Piensa cuáles son los errores en las siguientes soluciones incorrectas.

Ejemplo de solución incorrecta 1

bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   if (n == nullptr)
      return false;
   if (unDato < n->dato)
      buscar(unDato, n->izquierdo);
   if (unDato > n->dato)
      buscar(unDato, n->derecho);
   return true;
}

¿Por qué es incorrecta?

Esta solución es incorrecta, porque falta utilizar return para devolver el resultado de las llamadas recursivas.

Ejemplo de solución incorrecta 2

bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   if (unDato == n->dato)
      return true;
   else if (unDato < n->dato)
      return buscar(unDato, n->izquierdo);
   else
      return buscar(unDato, n->derecho);
}

¿Por qué es incorrecta?

Esta solución es incorrecta porque nunca devuelve false y nunca comprueba si n vale nullptr antes de utilizar n->.

Ejemplo de solución incorrecta 3

bool Conjunto::buscar(int unDato) const {
   if (raiz == nullptr)
      return false;
   else
      return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   if (unDato == n->dato)
      return true;
   else if (unDato < n->dato)
      return buscar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      return buscar(unDato, n->derecho);
   else
      return false;
}

Esta solución es incorrecta, porque no podemos acceder a n->dato ni n->izquierdo ni n->derecho si n vale nullptr, y porque la última instrucción return false no se puede alcanzar nunca debido a las condiciones de las instrucciones if previas.

Ejemplo de solución incorrecta 4

bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   if (unDato == n->dato)
      return true;
   if (n == nullptr)
      return false;
   return buscar(unDato, n->izquierdo) || buscar(unDato, n->derecho);
}

¿Por qué es incorrecta?

Esta solución es incorrecta, porque no podemos acceder a n->dato si n vale nullptr, y no está aprovechando que tenemos un árbol binario de búsqueda para decidir en cuál de los dos subárboles hay que seguir buscando.

Ejemplo de solución incorrecta 5 (opcional)

Un estudiante se ha puesto personalmente el reto de obtener el resultado sin utilizar ningún if, y ha llegado a la siguiente solución, que no funciona correctamente. ¿Serías capaz de encontrar su error?

bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   return n != nullptr && (n->dato == unDato || unDato < n->dato ? buscar(unDato, n->izquierdo) : buscar(unDato, n->derecho));
}

¿Por qué es incorrecta?

Le ha faltado simplemente utilizar paréntesis para que el operador || no se evalúe como parte del operando izquierdo del operador ?:

bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

bool Conjunto::buscar(int unDato, Nodo * n) const {
   return n != nullptr && (n->dato == unDato || (unDato < n->dato ? buscar(unDato, n->izquierdo) : buscar(unDato, n->derecho)));
}