Intentando hacer un recorrido en amplitud primero (orden por niveles) pero cayendo en un bucle infinito.
He estado trabajando en esto durante un buen rato y no puedo encontrar una manera de terminar el bucle. No estoy seguro si siquiera estoy en el camino correcto. Estoy intentando hacer un recorrido en anchura (orden por niveles) y aplicar una devolución de llamada en cada nodo durante el recorrido.
Aquí está la función constructora y el método para hacer la búsqueda en anchura…
function BinarySearchTree(value) {
this.value = value;
this.right = null;
this.left = null;
}
BinarySearchTree.prototype.add = function(value) {
if (value < this.value) {
if (this.left) {
this.left.add(value);
} else {
this.left = new BinarySearchTree(value);
}
}
if (value > this.value) {
if (this.right) {
this.right.add(value);
} else {
this.right = new BinarySearchTree(value);
}
}
};
BinarySearchTree.prototype.breadthFirst = function(callback) {
let queue = [];
queue.push(this.value);
while (queue.length) {
queue.pop();
callback(this.value);
if (this.left) {
queue.push(this.left);
}
if (this.right) {
queue.push(this.right);
}
}
};
¿Alguna idea de por qué estoy obteniendo un bucle infinito? ¡Cualquier consejo o ayuda será muy apreciada!
ACTUALIZADO: Datos de muestra…
var array = [];
var func = function(value){ array.push(value); };
binarySearchTree.add(2);
binarySearchTree.add(3);
binarySearchTree.add(7);
binarySearchTree.add(6);
console.log(binarySearchTree.breadthFirst(func)); -> debería imprimir [ 5, 2, 3, 7, 6 ]
He intentado esto…
BinarySearchTree.prototype.breadthFirst = function(callback) {
const queue = [];
let queueLength = this.value.length;
if (queueLength) {
queueLength--;
callback(this.value);
if (this.left) {
queue.push(this.left);
this.left.breadthFirst(callback);
}
if (this.right) {
queue.push(this.right);
this.right.breadthFirst(callback);
}
}
};
y esto…
BinarySearchTree.prototype.breadthFirst = function(callback) {
const queue = [];
let queueLength = this.value.length;
while (queueLength) {
queueLength--;
callback(this.value);
if (this.left) {
queue.push(this.left);
callback(this.left);
}
if (this.right) {
queue.push(this.right);
callback(this.right);
}
}
};
además de otras variaciones y ¡todavía obtengo un array vacío como resultado!
davy.ai
Parece que no estás actualizando correctamente la cola y la longitud de la cola en tu función breadthFirst, lo que está causando un bucle infinito. Aquí tienes una forma de corregir la función:
En esta función actualizada, inicializamos la cola con el nodo raíz, y luego mientras la cola tenga elementos, desacolamos el primer nodo, aplicamos el callback a su valor, y luego encolamos sus hijos izquierdo y derecho si existen. Esto asegura que visitamos cada nodo solo una vez y evitamos bucles infinitos.