Leve-esimene vs sügavus-esimene puu liikumine Javascriptis

Kui otsime läbi puu, et leida, kas see sisaldab kindlat sõlme, on kaks algoritmi, mida saame ehitada. Saame puust mööda laius-esimene või sügavus-esimene lähenemist.

Esimese sügavuse meetod usub, et minnakse puu otsast võimalikult kaugele, kuni see jõuab tupikusse. Kui see on jõudnud nullväärtuseni, algab selle ülaosast varundamine ja toimub sama protsess.

Laius-esimene meetod proovib oma parima, et jääda võimalikult ülaosale. See läbib puud üks rida korraga ja vaatab kõiki tema õdesid-vendi. Jätkub seda seni, kuni jõuab viimasele reale.

Lihtsa sõlme ja puu klassi ehitamine

Klassis Node on konstruktor, millel on kaks omadust. Sellel on andmeomadus, et salvestada sõlme väärtus, ja laste atribuudil, et hoida lapsesõlmede massiivi. Meetodit add () saab kasutada puusse uute sõlmede lisamiseks ja eemaldamismeetod () eemaldab soovimatu alamsõlme.

Puuklassi ehitades on meil vaja ainult atribuuti, mis osutab esimesele sõlmele, mida nimetatakse ka juuriks.

Klassi Inside sees on koht, kus me ehitame oma DFS ja BFS otsingufunktsioonid, et otsida sõlmede puust.

Sügavuse esimene algoritm

Kontrollimaks, kas puu sisaldab DFS-i lähenemisviisi kasutades teatud väärtust, loome funktsiooni, mis käivitub juursõlme sisaldava kogumimassiivi kuulutamisel. Seejärel ehitame mõne aja silmuse, mis kestab seni, kuni massiivi sees pole enam väärtust.

DFS kasutab sõlmede puu alt liikumiseks virna. Deklareerime praeguse sõlme, nihutades massiivi esimese väärtuse välja. Selle sõlme abil kontrollime, kas selle andmed on võrdsed otsitava väärtusega. Kui see on võrdne, tagastame väärtuse True ja väljume funktsioonist. Kui sõlme väärtus ei ühti, lükkame selle sõlme lapsed massiivi ette, kui nad on olemas. Nihutame lapsed ette, sest DFS-i lähenemisviis soovib, et me enne õdede-vendade elementide kontrollimist läheksime puu otsas põhjani. Kui pärast kogu puu otsimist ei vasta ükski väärtus, tagastame funktsiooni lõpus vale.

Laiuse esimene algoritm

Pärast DFS-funktsiooni loomist näeb BFS-funktsioon välja väga sarnane, kuid ühe väikese erinevusega. BFS-i lähenemist kasutades tahame enne puu järgmisele reale minemist kontrollida kõiki õdede-vendade elemente. Selle saavutame järjekorda kasutades. Järjekord nõuab, et me kasutaksime sõlme laste käitlemisel tõmbamismeetodi asemel tõukemeetodit. Selle asemel, et võtta sõlme lapsed ja seada nad kogukogude massiivi ette, surume nad selle asemel lõpuni. See tagab, et kontrollime kõiki õdede-vendade elemente enne puu järgmisele reale minekut.

Millal kasutada BFS vs DFS?

Mõlemad algoritmid võivad abiks olla puu otsimisel väärtuse otsimiseks, kuid milline neist on parem? Kõik sõltub puu struktuurist ja sellest, mida otsite. Kui teate, et otsitav väärtus on ülaosale lähemal, võib BFS-lähenemine olla parem valik, kuid kui puu on väga lai ja mitte liiga sügav, võib DFS-lähenemine olla kiirem ja tõhusam. Pidage ainult meeles, et enne lähenemisviisi valimist peate määrama palju muid tegureid. Ma usun, et saate sellest aru!