První šířka stromu a hloubka stromu Traversal v Javascriptu

Když prohledáme strom, abychom zjistili, zda obsahuje určitý uzel, můžeme vytvořit dva algoritmy. Můžeme stromem procházet přístupem šířka-první nebo hloubka-první.

Hloubka-první metoda věří v jít tak daleko dolů strom jak je to možné, dokud nedosáhne slepé uličky. Jakmile zasáhne nulovou hodnotu, spustí se zpět nahoře a provede stejný proces.

Metoda první šířky se snaží udržet co nejblíže vrcholu. Prochází stromem po řadě po řadě a dívá se na všechny jeho sourozenecké uzly. To pokračuje, dokud nedosáhne poslední řady.

Vytvoření jednoduché třídy Node a Tree

Třída Node bude mít konstruktor se dvěma vlastnostmi. Bude mít datovou vlastnost pro uložení hodnoty uzlu a podřízenou vlastnost pro uložení pole podřízených uzlů. Metodu add () lze použít k přidání nových uzlů do stromu a metoda remove () odstraní nežádoucí podřízený uzel.

Při vytváření třídy Tree potřebujeme vlastnost, aby ukazovala na první uzel, také známý jako root.

Uvnitř třídy Tree je místo, kde vytváříme naše vyhledávací funkce DFS a BFS, abychom prohledávali Strom uzlů.

Hloubka-první algoritmus

Chcete-li zkontrolovat, zda strom obsahuje určitou hodnotu pomocí přístupu DFS, vytvoříme funkci, která začíná deklarováním pole kolekce, které bude obsahovat kořenový uzel. Poté vytvoříme smyčku while, která bude spuštěna, dokud uvnitř pole již nebude žádná hodnota.

DFS používá zásobník k procházení stromem uzlů. Aktuální uzel deklarujeme posunutím první hodnoty pole. V tomto uzlu zkontrolujeme, zda se jeho data rovná hodnotě, kterou hledáme. Pokud je stejná, vrátíme True a opustíme funkci. Pokud se hodnota uzlu neshoduje, přesuneme děti tohoto uzlu na přední stranu pole, pokud existují. Děti posuneme dopředu, protože přístup DFS chce, abychom před kontrolou jakéhokoli prvku sourozence šli až na dno stromu. Pokud po prohledání celého stromu neodpovídá žádná hodnota, vrátíme na konci naší funkce false.

Algoritmus šíře - první

Po vytvoření funkce DFS bude funkce BFS vypadat velmi podobně, ale s malým rozdílem. Když použijeme přístup BFS, chceme zkontrolovat všechny sourozenecké prvky před přechodem na další řadu stromu. Toho dosáhneme pomocí fronty. Fronta vyžaduje, abychom při manipulaci s podřízenými uzly použili metodu push místo metody unshift. Místo toho, abychom vzali děti uzlu a vložili je do přední části pole kolekcí, místo toho je posuneme na konec. Tím je zajištěno, že zkontrolujeme všechny sourozenecké prvky před přechodem na další řadu stromu.

Kdy použít BFS vs. DFS?

Oba algoritmy se mohou hodit při procházení stromem, aby hledaly hodnotu, ale který z nich je lepší? Vše záleží na struktuře stromu a na tom, co hledáte. Pokud víte, že hledaná hodnota je blíže k vrcholu, přístup BFS může být lepší volbou, ale pokud je strom velmi široký a ne příliš hluboký, může být přístup DFS rychlejší a efektivnější. Jen mějte na paměti, že existuje mnoho dalších faktorů, které budete muset určit, než se rozhodnete, který přístup zvolit. Věřím, že na to přijdete!