Breiten erste Traversal eines Baum in Javascript

Question

ich versuche zu Datenstrukturen gut zu lernen und implementiert den folgenden Code für eine Depth-First-Traversal/Anwendung eines Rückrufes auf einem regelmäßigen Baum:

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); 
    } 
}; 

Wie konnte Ich ändere das, um es stattdessen zuerst zu erweitern. Diese ist, was der Baum-Klasse wie folgt aussieht:

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

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

    return newTree; 
}; 

Answer 1

Grundsätzlich ist die Differenz zwischen DFS und BFS ist, dass mit einer DFS Sie die Kinder des aktuellen Knotens auf einen Stapel schieben, so werden sie aufgetaucht und verarbeitet vor alles andere, während für BFS schieben Sie die Kinder auf das Ende einer Warteschlange, so dass sie geknallt und verarbeitet werden nach alles andere.

DFS ist rekursiv einfach zu implementieren, da Sie den Aufrufstapel als Stapel verwenden können. Mit BFS ist das nicht möglich, da Sie eine Warteschlange benötigen. Nur um die Ähnlichkeit deutlich zu machen, lässt Ihre DFS auf eine iterative Implementierung zuerst konvertieren:

//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]); 
    } 
    } 
}; 

Und jetzt 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]); 
    } 
    } 
};