Breadth-first vs Depth-first Tree Traversal in Javascript

Quando cerchiamo un albero per scoprire se contiene un certo nodo, ci sono due algoritmi che possiamo costruire. Possiamo attraversare l'albero con un approccio largo in primo luogo o in profondità.

Il metodo del primo in profondità crede di scendere il più lontano possibile dall'albero fino a raggiungere un vicolo cieco. Una volta raggiunto un valore nullo, inizia il backup dall'alto e segue lo stesso processo.

Il metodo breadth-first fa del suo meglio per rimanere il più vicino possibile. Attraversa l'albero una fila alla volta e osserva tutti i suoi nodi fratelli. Continua fino a quando non raggiunge l'ultima riga.

Creazione di una classe Node e Tree semplice

La classe Node avrà un costruttore con due proprietà. Avrà una proprietà data per memorizzare il valore del nodo e una proprietà children per contenere una matrice di nodi figlio. Il metodo add () può essere utilizzato per aggiungere nuovi nodi all'albero e il metodo remove () eliminerà un nodo figlio indesiderato.

Quando si crea una classe Tree, è necessaria solo una proprietà per puntare al primo nodo, noto anche come root.

All'interno della classe Tree è dove costruiamo le nostre funzioni di ricerca DFS e BFS per cercare in un albero di nodi.

Algoritmo profondità-primo

Per verificare che un albero contenga un determinato valore utilizzando l'approccio DFS, creeremo una funzione che inizia dichiarando l'array di raccolte, che conterrà il nodo principale. Costruiremo quindi un ciclo while che verrà eseguito fino a quando non vi sarà più un valore all'interno dell'array.

Il DFS utilizza uno Stack per attraversare l'albero dei nodi. Dichiareremo il nodo corrente spostando il primo valore dell'array. Con questo nodo, verificheremo se i suoi dati sono uguali al valore che stiamo cercando. Se è uguale, restituiremo True e usciremo dalla funzione. Se il valore del nodo non corrisponde, sposteremo i figli di quel nodo in primo piano nell'array se esistono. Spostiamo i bambini in primo piano perché l'approccio DFS vuole che arriviamo fino in fondo all'albero prima di controllare qualsiasi elemento fratello. Se nessun valore corrisponde dopo aver cercato l'intero albero, restituiamo false alla fine della nostra funzione.

Algoritmo primo

Dopo aver creato la funzione DFS, la funzione BFS apparirà molto simile, ma con una piccola differenza. Quando utilizziamo l'approccio BFS, vogliamo controllare tutti gli elementi di pari livello prima di passare alla riga successiva dell'albero. Lo faremo usando una Coda. La coda richiede che utilizziamo il metodo push anziché il metodo unshift quando gestiamo i figli del nodo. Invece di prendere i figli di un nodo e metterli in primo piano nell'array delle raccolte, li spingeremo invece fino alla fine. Questo assicurerà che controlleremo tutti gli elementi di pari livello prima di passare alla riga successiva dell'albero.

Quando utilizzare BFS vs. DFS?

Entrambi gli algoritmi possono tornare utili quando si attraversa un albero per cercare un valore, ma quale è meglio? Tutto dipende dalla struttura dell'albero e da cosa stai cercando. Se sai che il valore che stai cercando è più vicino all'inizio, un approccio BFS potrebbe essere una scelta superiore, ma se un albero è molto ampio e non troppo profondo, un approccio DFS potrebbe essere più veloce ed efficiente. Tieni presente che ci sono molti altri fattori che dovrai determinare prima di scegliere quale approccio adottare. Ho fiducia che lo capirai!