Breedte-eerst versus diepte-eerst Tree Traversal in Javascript

Wanneer we door een boom zoeken om te vinden of deze een bepaald knooppunt bevat, kunnen we twee algoritmen bouwen. We kunnen de boom doorkruisen met een breedte-eerst of diepte-eerste benadering.

De diepte-eerste methode gelooft in zo ver mogelijk door de boom te gaan tot het een doodlopende weg bereikt. Zodra het een nulwaarde bereikt, start het bovenaan en volgt hetzelfde proces.

De breedste methode probeert zijn best zo dicht mogelijk bij de top te houden. Het doorkruist de boom rij voor rij en kijkt naar al zijn broers en zussen. Dit gaat door totdat het de laatste rij bereikt.

Een eenvoudige Node- en Tree-klasse bouwen

De klasse Node heeft een constructor met twee eigenschappen. Het heeft een gegevenseigenschap om de waarde van het knooppunt op te slaan en een eigenschap child om een ​​reeks onderliggende knooppunten te bevatten. De methode add () kan worden gebruikt om nieuwe knooppunten aan de structuur toe te voegen en de methode remove () verwijdert een ongewenste onderliggende knoop.

Bij het bouwen van een Tree-klasse hebben we alleen een eigenschap nodig die naar de eerste knoop verwijst, ook bekend als de root.

Binnen de Tree-klasse bouwen we onze DFS- en BFS-zoekfuncties om door een Tree of nodes te zoeken.

Diepte-eerste algoritme

Om te controleren of een boom een ​​bepaalde waarde bevat met behulp van de DFS-benadering, maken we een functie die begint met het declareren van de collecties-array, die het root-knooppunt zal bevatten. We zullen dan een while-lus bouwen die loopt totdat er geen waarde meer in de array zit.

De DFS gebruikt een stapel om door de boom met knooppunten te bladeren. We declareren het huidige knooppunt door de eerste waarde van de array uit te schakelen. Met dit knooppunt controleren we of de gegevens gelijk zijn aan de waarde waarnaar we zoeken. Als het gelijk is, zullen we True retourneren en de functie verlaten. Als de waarde van het knooppunt niet overeenkomt, zullen we de kinderen van dat knooppunt naar de voorkant van de array duwen als ze bestaan. We verplaatsen de kinderen naar voren omdat de DFS-aanpak wil dat we helemaal naar de onderkant van de boom gaan voordat we een element van een broer of zus controleren. Als na het doorzoeken van de hele boom geen waarde overeenkomt, retourneren we false aan het einde van onze functie.

Grootste algoritme

Nadat de DFS-functie is gebouwd, ziet de BFS-functie er ongeveer hetzelfde uit, maar met een klein verschil. Wanneer we de BFS-aanpak gebruiken, willen we alle elementen van broers en zussen controleren voordat we naar de volgende rij van de boom gaan. We zullen dit bereiken door een wachtrij te gebruiken. De wachtrij vereist dat we de push-methode gebruiken in plaats van de unshift-methode bij het omgaan met de kinderen van het knooppunt. In plaats van de kinderen van een knooppunt te plaatsen en ze vooraan in de collectieserie te plaatsen, zullen we ze in plaats daarvan tot het einde duwen. Dit zorgt ervoor dat we alle elementen van broers en zussen zullen controleren voordat we naar de volgende rij van de boom gaan.

Wanneer BFS versus DFS gebruiken?

Beide algoritmen kunnen van pas komen bij het doorkruisen van een boom om een ​​waarde te zoeken, maar welke is beter? Het hangt allemaal af van de structuur van de boom en wat u zoekt. Als u weet dat de waarde die u zoekt dichter bij de top ligt, is een BFS-aanpak misschien een superieure keuze, maar als een boom erg breed en niet te diep is, kan een DFS-aanpak sneller en efficiënter zijn. Houd er rekening mee dat er nog vele andere factoren zijn die u moet bepalen voordat u kiest welke aanpak u wilt gebruiken. Ik heb er vertrouwen in dat je er wel uit komt!