Javascript-də çörək ilk vs Dərinlik birinci Traversal

Bir ağacın içərisində müəyyən bir nodun olub olmadığını tapmaq üçün araşdırdığımız zaman quracağımız iki alqoritm var. Ağacın genişliyinə və ya dərinliyinə ilk yanaşma ilə keçə bilərik.

Dərinliyə görə ilk üsul metoddan mümkün qədər aşağıya doğru enməyə inanır. Yalnış bir dəyəri vurduqdan sonra yuxarıdan geri çəkilməyə başlayır və eyni prosesi izləyir.

Genişlik ilk metodu mümkün qədər yuxarıya yaxın olmağa çalışır. Ağacı bir-bir sıradan keçir və bütün bacı düyünlərinə baxır. Bunu son sıraya çatana qədər davam etdirir.

Sadə Node və Ağac sinifinin qurulması

Node sinifində iki xüsusiyyətə sahib bir konstruktor olacaqdır. Düyün dəyərini saxlamaq üçün bir məlumat mülkiyyətinə və uşaq qovşaqlarının bir sıra keçirmək üçün bir uşaq əmlakına sahib olacaqdır. Əlavə et () metodu Ağacın yeni qovşaqlarını əlavə etmək üçün istifadə edilə bilər və qaldırmaq () metodu istənməyən uşaq nodunu silməkdədir.

Bir ağac sinfi qurarkən, yalnız kök kimi tanınan ilk node işarə etmək üçün bir əmlaka ehtiyacımız var.

Ağac sinifinin içərisində DFS və BFS axtarış funksiyalarımızı qovşaqların bir ağacı vasitəsilə axtarmaq üçün qururuq.

Dərinlik - Birinci Alqoritm

Bir ağacın DFS yanaşmasından istifadə edərək müəyyən bir dəyəri ehtiva etdiyini yoxlamaq üçün, kök düyünü ehtiva edən kolleksiyalar massivini elan etməklə başlayan bir funksiya yaradacağıq. Bundan sonra serialın içərisində artıq bir dəyər qalmayana qədər işləyəcək bir müddət düzəldəcəyik.

DFS düyünlər ağacının altından keçmək üçün bir yığını istifadə edir. Cari nodeu serialın ilk dəyərini dəyişərək elan edəcəyik. Bu node ilə məlumatların axtardığımız dəyərə bərabər olub olmadığını yoxlayacağıq. Əgər bərabərdirsə, True-u qaytaracağıq və funksiyadan çıxırıq. Düyünün dəyəri uyğun gəlmirsə, bu nodun uşaqlarını mövcud olduqda massivin ön tərəfinə itələyəcəyik. Uşaqları ön tərəfə qaldırırıq, çünki DFS yanaşması, hər hansı bir bacı elementini yoxlamadan əvvəl ağacın dibinə getməyimizi istəyir. Bütün ağacı axtardıqdan sonra heç bir dəyər uyğun gəlmirsə, funksiyamızın sonunda saxta qayıdırıq.

Çörək - Birinci Alqoritm

DFS funksiyasını qurduqdan sonra BFS funksiyası çox bənzər görünəcək, ancaq bir kiçik fərqlə. BFS yanaşmasından istifadə edərkən, ağacın növbəti sətirinə getmədən əvvəl bütün bacı elementlərini yoxlamaq istəyirik. Bunu bir növbədən istifadə etməklə həyata keçirəcəyik. Queue, düyünün uşaqlarını işləyərkən sökmə metodunun əvəzinə təkan metodundan istifadə etməyimizi tələb edir. Bir node övladlarını götürüb koleksiyonlar serialının ön hissəsinə qoymaq əvəzinə onları sona qədər itələyəcəyik. Bu, ağacın növbəti sətirinə getmədən əvvəl bütün bacı elementlərini yoxlayacağımıza əmin olur.

BFS vs DFS nə vaxt istifadə ediləcək?

Hər iki alqoritm bir dəyər axtarmaq üçün bir ağacdan keçərkən yararlı ola bilər, amma hansından daha yaxşıdır? Hamısı ağacın quruluşundan və nə axtardığınızdan asılıdır. Axtardığınız dəyərin yuxarıya yaxın olduğunu bilsəniz, BFS yanaşması üstün bir seçim ola bilər, ancaq bir ağac çox geniş və çox dərin deyilsə, DFS yanaşması daha sürətli və daha səmərəli ola bilər. Sadəcə unutmayın ki, hansı yanaşmanı seçmədən əvvəl müəyyənləşdirməli olduğunuz bir çox amil var. Bunu anlayacağınıza əminəm!