Lățime-prim-versus-adâncime-primul arbore transversal în Javascript

Când căutăm printr-un copac pentru a afla dacă conține un anumit nod, putem construi doi algoritmi. Putem traversa copacul cu o abordare de primă lățime sau de profunzime.

Metoda prim-adâncime crede în a merge cât mai departe în arbore, până când ajunge la un punct mort. Odată ce atinge o valoare nulă, aceasta începe din nou în partea de sus și urmează același proces.

Metoda pentru prima lățime încearcă tot posibilul să rămână cât mai aproape de vârf. Traversează arborele pe un rând la un moment dat și privește toate nodurile sale. Continuă acest lucru până când ajunge în ultimul rând.

Construirea unei clase simple de noduri și arbori

Clasa nod va avea un constructor cu două proprietăți. Va avea o proprietate de date pentru a stoca valoarea nodului și o proprietate pentru copii pentru a deține o serie de noduri copil. Metoda add () poate fi folosită pentru a adăuga noi noduri în Arbore și metoda remove () va șterge un nod copil nedorit.

Când construim o clasă Tree, avem nevoie doar de o proprietate pentru a indica primul nod, cunoscut și sub numele de rădăcină.

În cadrul clasei Tree este locul în care construim funcțiile noastre de căutare DFS și BFS pentru a căuta printr-un Arbore de noduri.

Profund-Primul Algoritm

Pentru a verifica pentru a vedea un arbore conține o anumită valoare folosind abordarea DFS, vom crea o funcție care începe prin declararea tabloul de colecții, care va conține nodul rădăcină. Vom construi apoi o buclă de timp care va rula până când nu mai există o valoare în interiorul tabloului.

DFS folosește un Stack pentru a traversa arborele nodurilor. Vom declara nodul curent prin mutarea primei valori a tabloului. Cu acest nod, vom verifica dacă datele sale sunt egale cu valoarea pe care o căutăm. Dacă este egal, vom returna True și vom ieși din funcție. Dacă valoarea nodului nu se potrivește, îi vom împinge pe copiii acelui nod în fața tabloului, dacă există. Dezlipim copiii în față, deoarece abordarea DFS vrea ca noi să mergem până la fundul copacului înainte de a verifica orice element de fratele. Dacă nicio valoare nu se potrivește după căutarea întregului arbore, revenim false la sfârșitul funcției noastre.

Algoritmul lărgimii

După construirea funcției DFS, funcția BFS va arăta foarte asemănător, dar cu o mică diferență. Când folosim abordarea BFS, dorim să verificăm toate elementele fraților înainte de a merge la rândul următor al arborelui. Vom realiza acest lucru folosind o coadă. Coada ne solicită să folosim metoda push în loc de metoda unshift la manipularea copiilor nodului. În loc să-i luăm pe copiii unui nod și să-i așezăm în partea din față a tabloului de colecții, în schimb îi vom împinge până la sfârșit. Acest lucru se asigură că vom verifica toate elementele de frați înainte de a merge la rândul următor al arborelui.

Când să folosiți BFS vs. DFS?

Ambii algoritmi pot veni la îndemână atunci când parcurgeți un copac pentru a căuta o valoare, dar care este mai bun? Totul depinde de structura arborelui și de ceea ce căutați. Dacă știți că valoarea pe care o căutați este mai aproape de partea de sus, o abordare BFS ar putea fi o alegere superioară, dar dacă un arbore este foarte larg și nu prea adânc, o abordare DFS ar putea fi mai rapidă și mai eficientă. Doar rețineți că există mulți alți factori pe care va trebui să-i determinați înainte de a alege ce abordare trebuie să luați. Am încredere că o vei da seama!