Širina prvega proti globini prvega drevesa v Javascriptu

Ko iščemo drevo in ugotovimo, ali vsebuje določeno vozlišče, lahko sestavimo dva algoritma. Drevo lahko prečkamo s pristopom po širini ali globini.

Prva metoda globine verjame, da gremo čim dlje po drevesu, dokler ne dosežemo slepo ulico. Ko doseže ničelno vrednost, se začne vrniti gor na vrhu in sledi istemu postopku.

Metoda prve širine se trudi, da ostane čim bližje vrhu. Po drevesu prečka eno vrstico in si ogleda vsa njegova sorodna vozlišča. To nadaljuje, dokler ne doseže zadnje vrstice.

Izdelava preprostega razreda vozlišč in dreves

Razred Node bo imel konstruktor z dvema lastnostma. Imela bo podatkovno lastnost za shranjevanje vrednosti vozlišča in otroške lastnosti, da hrani niz nadrejenih vozlišč. Metodo add () lahko uporabimo za dodajanje novih vozlišč v Drevo, metoda remove () pa izbriše neželeno nadrejeno vozlišče.

Pri gradnji razreda Tree potrebujemo samo lastnost, ki kaže na prvo vozlišče, znano tudi kot koren.

Znotraj razreda Tree gradimo naše iskalne funkcije DFS in BFS za iskanje po drevesu vozlišč.

Globina-prvi algoritem

Če želite preveriti, ali drevo vsebuje določeno vrednost s pristopom DFS, bomo ustvarili funkcijo, ki se začne z deklaracijo matrike zbirke, ki bo vsebovala korensko vozlišče. Nato bomo zgradili zanko za čas, ki se bo izvajala, dokler znotraj matrike ni več vrednosti.

DFS uporablja sklad za premikanje po drevesu vozlišč. Sprostili bomo trenutno vozlišče tako, da bomo odstranili prvo vrednost matrike. S tem vozliščem bomo preverili, ali so njegovi podatki enaki vrednosti, ki jo iščemo. Če je enaka, vrnemo True in izstopimo iz funkcije. Če se vrednost vozlišča ne ujema, bomo potisnili otroke tega vozlišča na sprednji del matrike, če obstajajo. Otroke premaknemo naprej, ker DFS želi, da gremo vse do dna drevesa, preden preverimo kateri koli bračni element. Če se po pregledu celotnega drevesa nobena vrednost ne ujema, na koncu funkcije vrnemo napačno.

Algoritem prvega širine

Po izdelavi funkcije DFS bo funkcija BFS videti zelo podobna, vendar z eno majhno razliko. Ko uporabljamo pristop BFS, želimo preveriti vse bratske elemente, preden se odpravimo do naslednje vrstice drevesa. To bomo dosegli z uporabo čakalne vrste. Čakalna vrsta zahteva, da pri rokovanju z otrokom vozlišča uporabimo metodo potiskanja namesto metode premikanja. Namesto, da vzamemo otroke vozlišča in jih nastavimo na sprednji del zbirke, jih bomo potisnili do konca. To zagotavlja, da bomo preverili vse bratske elemente, preden se odpravimo do naslednje vrstice drevesa.

Kdaj uporabljati BFS v primerjavi z DFS?

Oba algoritma sta lahko koristna, ko se pomikate po drevesu in poiščete vrednost, kateri pa je boljši? Vse je odvisno od strukture drevesa in tega, kar iščete. Če veste, da je vrednost, ki jo iščete, bližje vrhu, je morda pristop BFS odlična izbira, če pa je drevo zelo široko in ne pregloboko, bi bil DFS pristop hitrejši in učinkovitejši. Upoštevajte le, da obstaja veliko drugih dejavnikov, ki jih boste morali določiti, preden se odločite za pristop. Prepričan sem, da boste to ugotovili!