מעבר רוחב ראשון לעומת עומק ראשונה בעץ ב- Javascript

כאשר אנו מחפשים בעץ כדי למצוא אם הוא מכיל צומת מסוים, ישנם שני אלגוריתמים שנוכל לבנות. אנו יכולים לחצות את העץ בגישה ראשונה או ראשונה בעומק.

השיטה הראשונה העומק מאמינה לרדת ככל האפשר עד לעץ עד שתגיע למבוי סתום. ברגע שהוא פוגע בערך null, הוא מתחיל לגבות בחלקו העליון ועוקב אחר אותו תהליך.

שיטת הרוחב הראשונה מנסה כמיטב יכולתה להישאר קרוב ככל האפשר לראש. הוא חוצה את העץ שורה אחת בכל פעם ומסתכל על כל צמתי האחים שלו. זה ממשיך כך עד שהוא מגיע לשורה האחרונה.

בניית כיתת צמתים ועץ פשוטה

בכיתת הצומת יהיה בנאי עם שני תכונות. יהיה לו מאפיין נתונים לאחסון הערך של הצומת ונכס לילדים להחזקת מערך של צמתים לילד. ניתן להשתמש בשיטת הוספה () כדי להוסיף צמתים חדשים לעץ ושיטת הסר () תמחק צומת ילדים לא רצויים.

בבניית כיתת עץ, אנו זקוקים רק לנכס שמצביע על הצומת הראשון, המכונה גם השורש.

בתוך מעמד העץ הוא המקום בו אנו בונים את פונקציות DFS ו- BFS שלנו לחיפוש דרך עץ הצמתים.

אלגוריתם עומק-ראשון

כדי לבדוק אם עץ מכיל ערך מסוים בגישת DFS, ניצור פונקציה שמתחילה בהכרזת מערך האוספים, שיכיל את צומת השורש. לאחר מכן נבנה לולאת זמן שתפעל עד שלא יהיה עוד ערך בתוך המערך.

ה- DFS משתמש בערימה כדי לעבור במורד עץ הצמתים. אנו נכריז על הצומת הנוכחי על ידי הסרת הערך הראשון של המערך. בעזרת צומת זה נבדוק אם הנתונים שלו שווים לערך אותו אנו מחפשים. אם זה שווה, נחזיר נכון ונצא מהפונקציה. אם ערך הצומת אינו תואם, נדחוף את ילדי הצומת הזה לקדמת המערך אם הם קיימים. אנו מתירים את הילדים מקדימה מכיוון שגישת ה- DFS מעוניינת שנלך עד לקרקעית העץ לפני שנבדוק אלמנט אח כלשהו. אם שום ערך לא תואם לאחר חיפוש בכל העץ, אנו חוזרים כוזבים בסוף הפונקציה שלנו.

אלגוריתם רוחב ראשון

לאחר בניית פונקציית DFS, פונקציית BFS תיראה דומה מאוד, אך עם הבדל אחד קטן. כשאנחנו משתמשים בגישה BFS, אנו רוצים לבדוק את כל מרכיבי האחים לפני שנלך לשורה הבאה של העץ. אנו נעשה זאת באמצעות תור. התור דורש מאיתנו להשתמש בשיטת הדחיפה במקום בשיטת ה- Unshift בעת הטיפול בילדי הצומת. במקום לקחת את ילדי הצומת ולהכניס אותם לחזית מערך האוספים, אנו נדחוף אותם עד הסוף. זה מוודא כי נבדוק את כל מרכיבי האח לפני שנלך לשורה הבאה של העץ.

מתי להשתמש ב- BFS לעומת DFS?

שני האלגוריתמים יכולים להועיל כשאתם עוברים דרך עץ כדי לחפש ערך, אך איזה מהם עדיף? הכל תלוי במבנה העץ ובמה שאתה מחפש. אם אתה יודע שהערך שאתה מחפש קרוב יותר לפסגה, גישה BFS עשויה להיות בחירה מעולה, אך אם עץ רחב מאוד ולא עמוק מדי, גישה DFS עשויה להיות מהירה ויעילה יותר. רק קחו בחשבון שישנם גורמים רבים אחרים שתצטרכו לקבוע לפני שתבחרו איזו גישה לנקוט. יש לי ביטחון שתגלה את זה!