Breite erste Suche binäre Suche Baum Javascript-Implementierung

Question

Ich habe den folgenden Code, der eine BST-Struktur in JavaScript implementiert.

function Node(value) { 
    this.left = null; 
    this.right = null; 
    this.value = value; 
} 

function BinarySearchTree() { 
    this.root = null; 
    return; 
} 

BinarySearchTree.prototype.push = function(value) { 

    if (!this.root) { 
    this.root = new Node(value); 
    return; 
    } 

    var currentRoot = this.root; 
    var newNode = new Node(value); 
    while (currentRoot) { 
    if (value < currentRoot.value) { 
     if (!currentRoot.left) { 
     currentRoot.left = newNode; 
     break; 
     } else { 
     currentRoot = currentRoot.left; 
     } 
    } else { 

     if (!currentRoot.right) { 
     currentRoot.right = newNode; 
     break; 
     } else { 
     currentRoot = currentRoot.right; 
     } 

    } 

    } 

} 

var a = new BinarySearchTree(); 
a.push(27); 
a.push(14); 
a.push(35); 
a.push(10); 
a.push(19); 
a.push(31); 
a.push(42); 

Ich versuche, eine Funktion zu implementieren, die eine Breite ersten Traversal des Baumes tun. Das habe ich bisher versucht.

console.log(a.root.value); 
traverse(a.root); 

//function to traverse 
function traverse(node) { 

    currentNode = node; 
    while (currentNode.left) { 
    displayNodes(currentNode); 
    parent = currentNode; 
    currentNode = currentNode.left; 
    displayNodes(currentNode); 
    if(parent.right!=null){ 
    displayNodes(parent.right); 
    } 
    } 
} 

//function that displays the left and right node of a node 
function displayNodes(node) { 


    if (node.left != null) { 
    console.log(node.left.value); 
    } 
    if (node.right != null) { 
    console.log(node.right.value); 
    } 
} 

Ich bin nicht in der Lage, eine Funktion zu implementieren, die mit einer großen Anzahl von Daten skalieren konnte. Ich bin mir nicht sicher, ob eine rekursive Methode besser wäre oder eine while-Schleife. Wie kann ich die Funktion implementieren? Ich weiß, dass die Funktion zu unerwartetem Verhalten führt. Welche Korrektur soll ich machen?

Answer 1

Sie durchlaufen derzeit den Pfad vom Stammknoten zum linken Blatt.

Eine einfache nichtrekursiven Breadth-First-Traversal-Funktion einen Rückruf auf jedem durchlaufen Knoten Aufruf könnte wie folgt aussehen:

// Breadth-first traversal: 
function traverse(node, cb) { 
    var current = [node]; 
    while (current.length > 0) { 
    var next = []; 
    for (var node of current) { 
     cb(node); 
     if (node.left) next.push(node.left); 
     if (node.right) next.push(node.right); 
    } 
    current = next; 
    } 
} 

// Example: 
traverse(root, function(node) { 
    console.log(node.value); 
}); 

Es funktioniert durch eine Reihe von bereits entdeckt oder durchlaufen Knoten current halten, welche anfänglich nur Dein Wurzelknoten. Jetzt ersetzen Sie iterativ jeden Knoten in dieser Liste durch seine untergeordneten Elemente. In der obigen Funktion sind die Kinder in einem next Array gespeichert. Am Ende jeder Iteration werden alle Knoten der aktuellen Ebene in current durch alle ihre untergeordneten Elemente der nächst tieferen Ebene in next ersetzt. Siehe auch den ersten Vorschlag von @DavidKnipe's answer.

Ein nicht rekursiver Ansatz hat den Vorteil, dass er nicht der Größenbeschränkung für Callstacks unterliegt. Dies ermöglicht es Ihnen theoretisch, größere Datenstrukturen zu handhaben, wenn die call stack size is limited.

Answer 2

Wenn Sie nach einem Weg zu BFS mit O (1) Speicher suchen, glaube ich nicht, dass es eine gute Möglichkeit ist, es zu tun. (DFS ist jedoch eine andere Sache. Sind Sie sicher, es muss BFS sein?)

Es gibt zwei Möglichkeiten, die ich sehen kann, dies zu tun. Sie könnten mit dem Array [this.root] beginnen und eine Funktion schreiben, die über ein Array von Knoten iteriert und dann ein Array von untergeordneten Knoten dieser Knoten zurückgibt. Rufen Sie dann diese Funktion für das Array der untergeordneten Elemente auf, und fahren Sie mit dem Baum fort, bis Sie ein leeres Array erhalten.

Wenn Speicher ein Problem ist, gibt es einen anderen Weg, es zu tun. Anstatt sich das Array von Knoten auf einer bestimmten Ebene zu merken, können Sie sich nur die Tiefe merken und dann die Iteration jedes Mal wiederholen. Sie würden also eine Funktion haben, die eine natürliche Zahl n nimmt und über den Baum iteriert, aber ohne tiefer zu gehen als n, und tut, was immer Sie gerade versuchen, auf der Ebene n th; Rufen Sie diese Funktion dann für alle Werte von n auf, bis keine Knoten mehr übrig sind.

Diese letzte könnte sehr verschwenderisch klingen, aber es ist vielleicht nicht so schlimm, wenn die letzten Ebenen des Baumes die meisten Knoten enthalten. Dies hängt von Ihrem Dataset und Ihren Rechenfähigkeiten ab.