Indagamos en internet para tener para ti la solución para tu inquietud, si tienes dudas puedes dejarnos la duda y te respondemos con gusto, porque estamos para servirte.
Solución:
(Supongo que esto es solo algún tipo de ejercicio de pensamiento, o incluso una pregunta engañosa de tarea/entrevista, pero supongo que podría imaginar un escenario extraño en el que no se le permita ningún espacio de almacenamiento por alguna razón [some really bad custom memory manager? some bizarre runtime/OS issues?] mientras todavía tiene acceso a la pila…)
El recorrido primero en amplitud tradicionalmente usa una cola, no una pila. La naturaleza de una cola y una pila son bastante opuestas, por lo que tratar de usar la pila de llamadas (que es una pila, de ahí el nombre) como almacenamiento auxiliar (una cola) está condenado al fracaso, a menos que esté haciendo algo estúpidamente ridículo con la pila de llamadas que no deberías ser.
Del mismo modo, la naturaleza de cualquier recursión sin cola que intente implementar es esencialmente agregar una pila al algoritmo. Esto hace que ya no se busque primero en amplitud en un árbol binario y, por lo tanto, el tiempo de ejecución y otras cosas para BFS tradicional ya no se aplican por completo. Por supuesto, siempre puede convertir trivialmente cualquier bucle en una llamada recursiva, pero eso no es ningún tipo de recursividad significativa.
Sin embargo, hay formas, como lo demostraron otros, de implementar algo que sigue la semántica de BFS a algún costo. Si el costo de la comparación es alto pero el recorrido del nodo es barato, entonces, como lo hizo @Simon Buchan, simplemente puede ejecutar una búsqueda iterativa en profundidad, procesando solo las hojas. Esto significaría que no hay una cola creciente almacenada en el montón, solo una variable de profundidad local, y las pilas se acumulan una y otra vez en la pila de llamadas a medida que se recorre el árbol una y otra vez. Y como señaló @Patrick, un árbol binario respaldado por un array normalmente se almacena en el orden transversal primero en anchura de todos modos, por lo que una búsqueda en anchura primero en eso sería trivial, también sin necesidad de una cola auxiliar.
Si usas un array para respaldar el árbol binario, puede determinar el siguiente nodo algebraicamente. si i es un nodo, entonces sus hijos se pueden encontrar en 2i + 1 (para el nodo izquierdo) y 2i + 2 (para el nodo derecho). El siguiente vecino de un nodo viene dado por i + 1a no ser que i es un poder de 2
Aquí hay un pseudocódigo para una implementación muy ingenua de la búsqueda primero en amplitud en un array árbol de búsqueda binario respaldado. Esto asume un tamaño fijo array y por lo tanto un árbol de profundidad fija. Examinará los nodos sin padres y podría crear una pila inmanejablemente grande.
bintree-bfs(bintree, elt, i)
if (i == LENGTH)
return false
else if (bintree[i] == elt)
return true
else
return bintree-bfs(bintree, elt, i+1)
No pude encontrar una manera de hacerlo completamente recursivo (sin ninguna estructura de datos auxiliar). Pero si la cola Q se pasa por referencia, entonces puede tener la siguiente función recursiva de cola tonta:
BFS(Q)
if (
valoraciones y reseñas
No se te olvide difundir este artículo si si solucionó tu problema.