Breadth-first gegen Depth-first Tree Traversal in Javascript

Wenn wir einen Baum durchsuchen, um festzustellen, ob er einen bestimmten Knoten enthält, können wir zwei Algorithmen erstellen. Wir können den Baum mit einem Breitenzugriff oder einem Tiefenzugriff überqueren.

Bei der Methode der Tiefenschärfe geht es darum, den Baum so weit wie möglich zu senken, bis er eine Sackgasse erreicht. Sobald es einen Nullwert erreicht, wird es oben neu gestartet und folgt demselben Prozess.

Die Methode mit der ersten Breite versucht, so nah wie möglich an der Spitze zu bleiben. Es durchläuft den Baum zeilenweise und betrachtet alle seine Geschwisterknoten. Dies wird fortgesetzt, bis die letzte Reihe erreicht ist.

Erstellen einer einfachen Node and Tree-Klasse

Die Node-Klasse verfügt über einen Konstruktor mit zwei Eigenschaften. Die Eigenschaft data speichert den Wert des Knotens und die Eigenschaft children enthält ein Array von untergeordneten Knoten. Die add () -Methode kann verwendet werden, um dem Tree neue Knoten hinzuzufügen, und die remove () -Methode löscht einen unerwünschten untergeordneten Knoten.

Beim Erstellen einer Tree-Klasse benötigen wir nur eine Eigenschaft, die auf den ersten Knoten verweist, der auch als Root bezeichnet wird.

In der Tree-Klasse erstellen wir unsere DFS- und BFS-Suchfunktionen, um einen Baum von Knoten zu durchsuchen.

Tiefen-Erster Algorithmus

Um zu überprüfen, ob ein Baum einen bestimmten Wert enthält, erstellen wir mithilfe des DFS-Ansatzes eine Funktion, die zunächst das Collections-Array deklariert, das den Stammknoten enthält. Anschließend erstellen wir eine while-Schleife, die so lange ausgeführt wird, bis das Array keinen Wert mehr enthält.

Das DFS verwendet einen Stapel, um den Knotenbaum zu durchlaufen. Wir deklarieren den aktuellen Knoten, indem wir den ersten Wert des Arrays verschieben. Mit diesem Knoten prüfen wir, ob seine Daten dem gesuchten Wert entsprechen. Wenn es gleich ist, geben wir True zurück und verlassen die Funktion. Wenn der Wert des Knotens nicht übereinstimmt, verschieben wir die untergeordneten Elemente dieses Knotens an den Anfang des Arrays, sofern vorhanden. Wir schieben die Kinder nach vorne, weil die DFS vorsieht, dass wir den ganzen Weg bis zum Ende des Baumes zurücklegen, bevor wir ein Geschwisterelement überprüfen. Wenn nach dem Durchsuchen des gesamten Baums kein Wert übereinstimmt, geben wir am Ende unserer Funktion false zurück.

Breitenspiel-Algorithmus

Nach dem Erstellen der DFS-Funktion sieht die BFS-Funktion sehr ähnlich aus, mit einem kleinen Unterschied. Wenn wir den BFS-Ansatz verwenden, möchten wir alle Geschwisterelemente überprüfen, bevor wir zur nächsten Zeile des Baums gehen. Dies erreichen wir mit einer Queue. In der Warteschlange müssen wir die Push-Methode anstelle der Unhift-Methode verwenden, wenn wir die untergeordneten Elemente des Knotens behandeln. Anstatt die untergeordneten Elemente eines Knotens zu übernehmen und sie in den Vordergrund des Auflistungsarrays zu stellen, werden sie bis zum Ende verschoben. Dies stellt sicher, dass wir alle Geschwisterelemente überprüfen, bevor wir zur nächsten Zeile des Baums gehen.

Wann soll man BFS vs. DFS verwenden?

Beide Algorithmen können nützlich sein, wenn Sie durch einen Baum nach einem Wert suchen, aber welcher ist besser? Es hängt alles von der Struktur des Baumes und dem ab, wonach Sie suchen. Wenn Sie wissen, dass der Wert, den Sie suchen, näher an der Spitze liegt, ist ein BFS-Ansatz möglicherweise die beste Wahl. Wenn ein Baum jedoch sehr breit und nicht zu tief ist, ist ein DFS-Ansatz möglicherweise schneller und effizienter. Denken Sie daran, dass Sie noch viele andere Faktoren bestimmen müssen, bevor Sie sich für einen Ansatz entscheiden. Ich vertraue darauf, dass Sie es herausfinden werden!