es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

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!

Tags:  , , ,

Answer

  1. Avatar for 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:

    BinarySearchTree.prototype.breadthFirst = function(callback) {
      const queue = [this]; // inicializar la cola con el nodo raíz
      while (queue.length) {
        const currentNode = queue.shift();
        callback(currentNode.value);
        if (currentNode.left) {
          queue.push(currentNode.left);
        }
        if (currentNode.right) {
          queue.push(currentNode.right);
        }
      }
    };
    

    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.

Comments are closed.