Aquí está mi código dentro de una clase BinarySearchTree. No sé si es por el comportamiento de forEach, o porque en alguna parte de mi código está mal.
class BinarySearchTree { constructor() { this.root = null; } insert(val) { let newNode = new Node(val) if (!this.root) { this.root = newNode; return this; } else { let level = this.root // if (val < level.value && level.left){ // level = level.left while (true) { if (val < level.value) { if (level.left) { level = level.left } else if (!level.left) { level.left = newNode; return this } } else if (val > level.value) { if (level.right) { level = level.right } else if (!level.right) { level.right = newNode; return this } } } } } BFS() { let data = []; let queue = []; if (!this.root) { return false } else if (this.root) { queue.push(this.root) while (queue.length) { queue.forEach(function (element) { if (element.left) { queue.push(element.left) } if (element.right) { queue.push(element.right) } queue.shift() data.push(element) }) } return data } } } class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } }Aquí está la entrada
tree.insert(50) tree.insert(70) tree.insert(43) tree.insert(45) tree.insert(18) tree.insert(52) tree.insert(59) console.log(tree.BFS())Aquí está la salida
[ Node { value: 50, left: Node { value: 43, left: [Node], right: [Node] }, right: Node { value: 70, left: [Node], right: null } }, Node { value: 43, left: Node { value: 18, left: null, right: null }, right: Node { value: 45, left: null, right: null } }, Node { value: 18, left: null, right: null }, Node { value: 18, left: null, right: null }, Node { value: 45, left: null, right: null } ]Como puede ver, hay duplicaciones y también algunos nodos del árbol no se muestran en absoluto. ¡Gracias a todos de antemano!
Si llama a forEach , no debe modificar la matriz subyacente . Se producirán todo tipo de comportamientos difíciles de entender.
Como lo menciona @JDB, no debe modificar la matriz subyacente en forEach .
Aunque no necesita usar forEach para BFS en este caso, ya que solo está recorriendo el árbol. Puede procesar un elemento a la vez desde el principio de la cola hasta que la cola esté vacía.
class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(val) { let newNode = new Node(val) if (!this.root) { this.root = newNode; return this; } else { let level = this.root // if (val < level.value && level.left){ // level = level.left while (true) { if (val < level.value) { if (level.left) { level = level.left } else if (!level.left) { level.left = newNode; return this } } else if (val > level.value) { if (level.right) { level = level.right } else if (!level.right) { level.right = newNode; return this } } } } } BFS() { let data = []; let queue = []; if (!this.root) { return false } else if (this.root) { queue.push(this.root) while (queue.length) { const element = queue[0] data.push(element) if (element.left) { queue.push(element.left) } if (element.right) { queue.push(element.right) } queue.shift() } return data } } } const tree = new BinarySearchTree(); tree.insert(50) tree.insert(70) tree.insert(43) tree.insert(45) tree.insert(18) tree.insert(52) tree.insert(59) const result = tree.BFS() for (r of result) console.log(r)