Fyrsta breidd vs dýpt fyrsta trjágöng í Javascript

Þegar við leitum í gegnum tré til að finna hvort það inniheldur ákveðinn hnút, þá eru til tveir reiknirit sem við getum smíðað. Við getum farið yfir tréð með fyrstu breidd eða fyrstu dýpt.

Fyrsta dýptaraðferðin trúir á að fara eins langt niður í tréð og mögulegt er þar til hún nær blindgati. Þegar það hefur náð gildi, byrjar það aftur upp og fylgir sama ferli.

Breiddar-fyrsta aðferðin reynir sitt besta til að vera eins nálægt toppnum og mögulegt er. Það fer yfir tréð eina röð í einu og lítur á alla systkinahnútana. Það heldur þessu áfram þar til það nær síðustu röðinni.

Byggja upp einfaldan hnút og tré bekk

Node bekkurinn verður með smíðara með tvo eiginleika. Það mun hafa gagnaeign til að geyma gildi hnútins og barnaeign til að geyma fjölda barnahnúta. Hægt er að nota add () aðferðina til að bæta við nýjum hnútum í Tree og aðferðin remove () mun eyða óæskilegum hnút fyrir börn.

Þegar við byggjum trjástétt þurfum við aðeins eign til að vísa á fyrsta hnútinn, einnig þekktur sem rótin.

Inni í tréflokknum er þar sem við smíðum DFS og BFS leitaraðgerðir okkar til að leita í tré hnúta.

Dýpt-fyrsta reiknirit

Til að athuga hvort tré inniheldur ákveðið gildi með DFS nálgun, munum við búa til aðgerð sem byrjar með því að lýsa yfir söfnunarsviðinu, sem mun innihalda rótarhnútinn. Við munum þá byggja upp smálykkju sem mun keyra þar til það er ekki lengur gildi inni í fylkingunni.

DFS notar stafla til að fara niður hnúta tréð. Við munum lýsa yfir núverandi hnút með því að færa af fyrsta gildi fylkisins. Með þessum hnút munum við athuga hvort gögn þess séu jöfn gildinu sem við erum að leita að. Ef það er jafnt, munum við snúa aftur True og hætta út úr aðgerðinni. Ef gildi hnútsins passar ekki munum við ýta börnum þess hnút framan á fylkinguna ef þau eru til. Við skiptum börnunum að framan vegna þess að DFS nálgunin vill að við förum alla leið til botns í trénu áður en þú skoðar einhvern systkinaþátt. Ef ekkert gildi samsvarar eftir að hafa leitað í öllu trénu, skilum við ósatt í lok aðgerðar okkar.

Breidd - fyrsta reiknirit

Eftir að DFS hefur verið smíðað mun BFS aðgerðin líta mjög út, en með einum litlum mun. Þegar við notum BFS nálgunina viljum við athuga alla systkinaþætti áður en við förum í næstu röð trésins. Við munum ná þessu með því að nota biðröð. Biðröðin krefst þess að við notum ýtaaðferðina í stað óskiptunaraðferðar þegar við meðhöndlum börn hnútins. Í stað þess að taka börn á hnút og setja þau í framhlið safnkerfisins munum við í staðinn ýta þeim til loka. Þetta tryggir að við munum athuga alla systkinaþætti áður en við förum í næstu röð trésins.

Hvenær á að nota BFS vs. DFS?

Báðir reiknirit geta komið sér vel þegar þú ferð um tré til að leita að gildi, en hver er betri? Það veltur allt á uppbyggingu trésins og því sem þú ert að leita að. Ef þú veist að gildi sem þú ert að leita að er nær efst, gæti BFS nálgun verið framúrskarandi val, en ef tré er mjög breitt og ekki of djúpt, gæti DFS nálgun verið hraðari og skilvirkari. Hafðu bara í huga að það eru margir aðrir þættir sem þú þarft að ákvarða áður en þú velur hvaða aðferð þú vilt taka. Ég hef fullviss um að þú munt reikna það út!