breadth-first attraversamento di un albero in javascript

Question

Sto cercando di imparare bene le strutture di dati e implementato il seguente codice per una profondità prima attraversamento/applicazione di un callback su un albero normale:

Tree.prototype.traverse = function (callback) { 
    callback(this.value); 

    if (!this.children) { 
    return; 
    } 
    for (var i = 0; i < this.children.length; i++) { 
    var child = this.children[i]; 
    child.traverse(callback); 
    } 
}; 

Come potrebbe Io cambio questo per renderlo prima di tutto invece? Questo è ciò che la classe Tree assomiglia:

var Tree = function (value) { 
    var newTree = {}; 

    newTree.value = value; 
    newTree.children = []; 
    extend(newTree, treeMethods); 

    return newTree; 
}; 

Answer 1

Fondamentalmente, la differenza tra DFS e BFS è che con un DFS si spingono i figli del nodo corrente in uno stack, in modo che sarà spuntato e trattati prima di tutto il resto, mentre per BFS si spinge i bambini alla fine di una coda, quindi verranno spuntati e processati dopo il tutto il resto.

DFS è facile da implementare in modo ricorsivo perché è possibile utilizzare lo stack di chiamate come stack. Non puoi farlo con BFS, perché hai bisogno di una coda. Giusto per rendere la somiglianza evidente, consente di convertire i tuoi DFS per un'implementazione iterativa prima:

//DFS 
Tree.prototype.traverse = function (callback) { 
    var stack=[this]; 
    var n; 

    while(stack.length>0) { 

    n = stack.pop(); 
    callback(n.value); 

    if (!n.children) { 
     continue; 
    } 

    for (var i = n.children.length-1; i>=0; i--) { 
     stack.push(n.children[i]); 
    } 
    } 
}; 

E ora BFS

//BFS 
Tree.prototype.traverse = function (callback) { 
    var queue=[this]; 
    var n; 

    while(queue.length>0) { 

    n = queue.shift(); 
    callback(n.value); 

    if (!n.children) { 
     continue; 
    } 

    for (var i = 0; i< n.children.length; i++) { 
     queue.push(n.children[i]); 
    } 
    } 
};