הייצוג החזותי של המושגים הנדונים מוצג באיור שלהלן:
מדריך זה מסביר את תהליך הדפסת כל צמתי העלים של עץ בינארי על ידי כיסוי הסעיפים המוזכרים להלן:
- כיצד לזהות צמתים עלים?
- כיצד להדפיס את כל צמתי העלים של עץ בינארי משמאל לימין ב-JavaScript?
- טיפ בונוס: הדפסת צמתים עלים של עץ בינארי מימין לכיוון שמאל
- סיכום
כיצד לזהות צמתים עלים?
ה ' עלה ' צמתים הם אלה שאין להם צמתים צאצאים, או ליתר דיוק שיש להם את ' גוֹבַה 'של' 0 '. אם לצומת יש ' גוֹבַה ' גדול מ ' 0 ' אז הצומת הזה יכול להיות הצומת הפנימי או הצומת השורשי. ה ' עלה ' צמתים נגררים בדרך כלל לאחור כדי לזהות את המקור המקורי שממנו נוצר הצומת הזה. הוא משמש בעיקר באלגוריתמים של חיפוש או איתור שגיאות כדי למצוא את הסיבה לשגיאה או בעיה.
כיצד להדפיס את כל צמתי העלים של עץ בינארי משמאל לימין ב-JavaScript?
יש שתי גישות' רקורסיבי 'ו' איטרטיבי ' כדי לבחור את כל צמתי העלים הזמינים בעץ הבינארי המסופק ב' הרצוי ' שמאלה ' ל ' ימין ' כיוון. היישום המעשי של גישות אלה מודגם בסעיפים המפורטים להלן:
- הדפס את כל צמתי העלים של עץ בינארי משמאל לימין באופן רקורסיבי
- הדפס את כל צמתי העלים של עץ בינארי באמצעות הגישה האיטרטיבית
שיטה 1: הדפס את כל צמתי העלים של עץ בינארי משמאל לימין באופן רקורסיבי
הגישה הרקורסיבית בוחרת את כל הצמתים ב-a אלגוריתם חיפוש עומק ראשון אופן שחוצה תחילה את כל הצמתים בצד שמאל ואז את הצומת האמצעי ואת הצמתים בצד ימין בסוף. פעולה זו מתבצעת באופן רקורסיבי עבור כל צומת וכאשר אין חצייה נוספת של ' עלה ' צמתים זוהים. כדי להבין טוב יותר את המושג הזה, בקר בקטע הקוד שלהלן:
מעמד צוֹמֶת{
בַּנַאִי ( )
{
זֶה . תוֹכֶן = 0 ;
זֶה . שמאלה = ריק ;
זֶה . ימין = ריק ;
}
} ;
היכן מציגיםNodes = ( rootNode ) =>
{
אם ( rootNode == ריק )
לַחֲזוֹר ;
אם ( rootNode. שמאלה == ריק && rootNode. ימין == ריק )
{
מסמך. לִכתוֹב ( rootNode. תוֹכֶן + '' ) ;
לַחֲזוֹר ;
}
אם ( rootNode. שמאלה != ריק )
displayLeafNodes ( rootNode. שמאלה ) ;
אם ( rootNode. ימין != ריק )
displayLeafNodes ( rootNode. ימין ) ;
}
היה sampleNode = ( val ) =>
{
היה tempNode = חָדָשׁ צוֹמֶת ( ) ;
tempNode. תוֹכֶן = val ;
tempNode. שמאלה = ריק ;
tempNode. ימין = ריק ;
לַחֲזוֹר tempNode ;
}
היה rootNode = provNode ( 3 ) ;
rootNode. שמאלה = provNode ( 6 ) ;
rootNode. ימין = provNode ( 9 ) ;
rootNode. שמאלה . שמאלה = provNode ( 12 ) ;
rootNode. שמאלה . ימין = provNode ( חֲמֵשׁ עֶשׂרֵה ) ;
rootNode. שמאלה . ימין . ימין = provNode ( 24 ) ;
rootNode. ימין . שמאלה = provNode ( 18 ) ;
rootNode. ימין . ימין = provNode ( עשרים ואחת ) ;
displayLeafNodes ( rootNode ) ;
ההסבר של בלוק הקוד לעיל מצוין להלן:
- ראשית, צור כיתה בשם ' צוֹמֶת ', שיוצר צומת חדש ומגדיר את הערך שלו ל' 0 '. המצורף ' שמאלה 'ו' ימין ' צמתי צד מוגדרים ל' ריק ' כברירת מחדל באמצעות בנאי המחלקה.
- לאחר מכן, הגדר ' displayLeafNodes() ' פונקציה שמקבלת פרמטר בודד של ' rootNode '. ערך פרמטרי זה נחשב כצומת שנבחר כעת של עץ בינארי.
- בתוך הפונקציה, ' אם הצהרת ' משמשת כדי לבדוק אם ' rootNode 'בטל או לא. במקרה של ' ריק ' הביצוע הנוסף נעצר עבור אותו צומת. במקרה השני, ה-rootNode ' שמאלה 'ו' ימין ' צמתי צד מסומנים עבור ' ריק '. אם שניהם null, הערך של ' צוֹמֶת ' מודפס.
- אם ה' שמאלה ' או ' ימין ' הצומת אינו 'null', ואז העבירו את הצד הזה של הצומת ל-' displayLeafNodes() ' פונקציה לפעולה רקורסיבית.
- הגדר פונקציה חדשה בשם ' provNode() ' שמקבל את הפרמטר היחיד של ' val '. בתוך הפונקציה צור מופע חדש של ' צוֹמֶת 'כיתה בשם ' tempNode '. הקצה את הפרמטרי ' val 'כערך לנכס המחלקה' תוֹכֶן ' והגדר את ' שמאלה ' ו' ימין ' צמתי צד ל' ריק ' כברירת מחדל.
- לבסוף, צור אובייקט בשם ' rootNode ' בשביל ה ' provNode() ' פונקציה והעבירו את ערך הצומת כפרמטר פונקציה זה. צור את הצמתים בצד שמאל וימין על ידי הוספת ' שמאלה ' ו' ימין ' מילות מפתח עם 'rootNode' והקצו להן ערך באמצעות אותה פונקציה ' provNode() '.
- ה ' שמאלה ' פירושו המיקום השמאלי של צומת השורש וה' שמאלה שמאלה ' מיקום פירושו שמאלה משמאל אותה גישה מיושם במקרה של ' ימין ' ו' ימין ”
- לאחר הגדרת העץ, העבר את 'rootNode' כארגומנט עבור ' displayLeadNodes() ' פונקציה כדי לבחור ולהדפיס את כל צמתי העלים של העץ שנוצר.
הפלט שנוצר לאחר ההידור מאשר שצומת העלים של העץ שסופק אוחזר והודפס על גבי המסוף:
שיטה 2: הדפס את כל צמתי העלים של עץ בינארי באמצעות הגישה האיטרטיבית
ה ' איטרטיבי הגישה היא הגישה היעילה ביותר, היא משתמשת במושג ' לִדחוֹף ' ו' פּוֹפּ ' כדי לבחור את ' עלה ' צמתים. נקודות המפתח או פעולתה של גישה זו מצוינות להלן:
מעמד צוֹמֶת{
בַּנַאִי ( ערך )
{
זֶה . נתונים = ערך ;
זֶה . שמאלה = ריק ;
זֶה . ימין = ריק ;
}
} ;
היכן מציגיםNodes = ( rootNode ) =>
{
אם ( ! rootNode )
לַחֲזוֹר ;
תן רשימה = [ ] ;
רשימה. לִדחוֹף ( rootNode ) ;
בזמן ( רשימה. אורך > 0 ) {
rootNode = רשימה [ רשימה. אורך - 1 ] ;
רשימה. פּוֹפּ ( ) ;
אם ( ! rootNode. שמאלה && ! rootNode. ימין )
מסמך. לִכתוֹב ( rootNode. נתונים + '' ) ;
אם ( rootNode. ימין )
רשימה. לִדחוֹף ( rootNode. ימין ) ;
אם ( rootNode. שמאלה )
רשימה. לִדחוֹף ( rootNode. שמאלה ) ;
}
}
היה rootNode = חָדָשׁ צוֹמֶת ( 3 ) ;
rootNode. שמאלה = חָדָשׁ צוֹמֶת ( 6 ) ;
rootNode. ימין = חָדָשׁ צוֹמֶת ( 9 ) ;
rootNode. שמאלה . שמאלה = חָדָשׁ צוֹמֶת ( 12 ) ;
rootNode. שמאלה . ימין = חָדָשׁ צוֹמֶת ( חֲמֵשׁ עֶשׂרֵה ) ;
rootNode. שמאלה . ימין . ימין = חָדָשׁ צוֹמֶת ( 24 ) ;
rootNode. ימין . שמאלה = חָדָשׁ צוֹמֶת ( 18 ) ;
rootNode. ימין . ימין = חָדָשׁ צוֹמֶת ( עשרים ואחת ) ;
displayLeafNodes ( rootNode ) ;
ההסבר של הקוד לעיל כתוב להלן:
- ראשית, צור ' צוֹמֶת ' מחלקה שמקבלת פרמטר בודד ' ערך ” אשר מוגדר כערך של הצומת החדש שנוצר, והצד השמאלי והימני מוגדרים ל- null. בדיוק כמו שנעשה בדוגמה לעיל.
- לאחר מכן, צור פונקציה ' displayLeafNodes() ' שמקבל פרמטר בודד של ' rootNode '. 'rootNode' זה נחשב לעץ הבינארי והריקנות שלו נבדקת תחילה.
- אם הצומת לא ריק, אז רשימה ריקה בשם ' רשימה ' נוצר וה' rootNode פרמטר ' מוכנס אליו באמצעות ' לִדחוֹף() ' שיטה.
- אז ה ' בזמן() נעשה שימוש שמבצע עד אורך ' רשימה '. בתוך הלולאה, האלמנט השוכן בתחתית עץ או ' רשימה ' יוסר באמצעות ' פּוֹפּ() ' שיטה.
- כעת, קיומו של ' שמאלה ' ו' ימין ' הצדדים של 'rootNode' מסומנים, ואם שני הצדדים אינם קיימים זה אומר שאין לו צומת צאצא. לאחר מכן, צומת זה מוצג על המסך ומזוהה כצומת עלים.
- אם יש צומת בצד שמאל או ימין פירושו שיש לו ילדים. אז זה ' שמאלה ' ו' ימין צומת ' נדחף לתוך ' רשימה ' לפעולה נוספת של מציאת צומת העלה.
- בסופו של דבר, צור עץ בינארי מותאם אישית על ידי העברת ערכי הצומת כפרמטרים עבור ' צוֹמֶת 'בנאי מחלקה. לאחר היצירה, העבר את העץ 'rootNode' כטיעון עבור ' displayLeafNodes() ' פונקציה.
הפלט שנוצר לאחר ההידור מראה שצמתי העלים של העץ המסופק מודפסים:
טיפ בונוס: הדפסת צמתים עלים של עץ בינארי מימין לכיוון שמאל
כדי לאחזר את כל צמתי העלים שאין להם צמתים צאצאים ב' ימין ' ל ' שמאלה ” כיוון, הגישה הרקורסיבית היא המומלצת ביותר בשל הקלות שלה. לדוגמה, אותו עץ שנדון בסעיפים לעיל ישמש כדי לאחזר את צומת העלה אבל ב' ימין ' אל ה ' שמאלה ' כיוון, כפי שמוצג להלן:
מעמד צוֹמֶת{
בַּנַאִי ( ערך )
{
זֶה . נתונים = ערך ;
זֶה . שמאלה = ריק ;
זֶה . ימין = ריק ;
}
} ;
פונקציה displayLeafNodes ( שורש )
{
אם ( שורש == ריק )
{
לַחֲזוֹר ;
}
אם ( שורש. שמאלה == ריק && שורש. ימין == ריק )
{
מסמך. לִכתוֹב ( שורש. נתונים + '' ) ;
לַחֲזוֹר ;
}
אם ( שורש. ימין != ריק )
{
displayLeafNodes ( שורש. ימין ) ;
}
אם ( שורש. שמאלה != ריק )
{
displayLeafNodes ( שורש. שמאלה ) ;
}
}
היה rootNode = חָדָשׁ צוֹמֶת ( 3 ) ;
rootNode. שמאלה = חָדָשׁ צוֹמֶת ( 6 ) ;
rootNode. ימין = חָדָשׁ צוֹמֶת ( 9 ) ;
rootNode. שמאלה . שמאלה = חָדָשׁ צוֹמֶת ( 12 ) ;
rootNode. שמאלה . ימין = חָדָשׁ צוֹמֶת ( חֲמֵשׁ עֶשׂרֵה ) ;
rootNode. שמאלה . ימין . ימין = חָדָשׁ צוֹמֶת ( 24 ) ;
rootNode. ימין . שמאלה = חָדָשׁ צוֹמֶת ( 18 ) ;
rootNode. ימין . ימין = חָדָשׁ צוֹמֶת ( עשרים ואחת ) ;
displayLeafNodes ( rootNode ) ;
הקוד שצוין לעיל עובד כך:
- ראשית, הכיתה' צוֹמֶת נוצר שמשתמש בבנאי ברירת המחדל כדי להוסיף צומת חדש בעץ רק את הקישור שנעשה בדוגמאות לעיל.
- לאחר מכן, ה' displayLeadNodes() נוצרת פונקציה שמקבלת פרמטר בודד של ' rootNode '. פרמטר זה מסומן עבור ' ריק ' מצב באמצעות ' אם 'הצהרה.
- אם הצומת שסופק אינו נכון, אזי ' שמאלה ' ו' ימין ' צמתי צד מסומנים עבור ' ריק 'מצב. אם שניהם null, אז הצומת יזוהה בתור ' עלה ' צומת ומודפס על גבי דף האינטרנט.
- לאחר מכן, העבר את ' ימין ' ו' שמאלה ' צמתים של ' rootNode ' אל ה ' displayLeafNodes() ' פונקציה.
- הקצה את המיקום של כל צומת על ידי יצירת המופעים באמצעות ' חָדָשׁ ' מילת המפתח וה' צוֹמֶת() 'קונסטרוקטור וציון המיקום כפרמטר הבנאי.
- ה ' שמאלה ' פירושו המיקום השמאלי של צומת השורש וה' שמאלה שמאלה 'מיקום פירושו שמאלה או שמאלה. אותה גישה מיושמת במקרה של ' ימין ' ו' ימין '.
- לבסוף, העבר את ' rootNode ' כטענה ל' displayLeafNode() ' פונקציה.
הפלט שנוצר מראה שצמתי עלים מודפסים בכיוון מימין לשמאל.
זה הכל על הדפסת כל צמתי העלים של עץ בינארי בכל כיוון רצוי.
סיכום
כדי להדפיס את כל צמתי העלים של עץ בינארי, צור מחלקה אקראית שיוצרת ומקצה ערכים לצמתי העץ. לאחר מכן, צור פונקציה אקראית שמקבלת צומת בודד של העץ בהיררכיה מלמעלה למטה. פונקציה זו מכילה מספר ' אם ' תנאים הבודקים אם ' צוֹמֶת ' אינו ריק ואין לו צמתים ב' שמאלה ' ו' ימין כיוון ', אז הצומת הזה נחשב כ' עלה ' צומת ומוצג בקונסולה. מדריך זה הסביר את ההליך של הדפסת כל צמתי העלים של עץ בינארי משמאל לימין או מימין לשמאל.