מהו עץ בינארי מלא?
ניתן להגדיר עץ בינארי מלא בתור א עץ בינארי שבו לכל הצמתים יש 0 או שני ילדים. במילים אחרות, ניתן להגדיר את העץ הבינארי המלא כעץ בינארי שבו לכל הצמתים יש שני ילדים מלבד צמתי העלים.
העץ למטה הוא עץ בינארי מלא:
העץ הנ'ל הוא עץ בינארי מלא שכן לכל הצמתים מלבד צמתי העלים יש שני ילדים.
משפט העץ הבינארי המלא:
אם כן, ראה שעץ בינארי T הוא עץ לא ריק:
- תן לי להיות צמתים פנימיים בעץ ו-L להיות צומת עלים בעץ, אז מספר צמתים העלים יהיה שווה ל:
L = I + 1 - אם ל-T יש מספר I של צמתים פנימיים ו-N הוא המספר הכולל של צמתים, אז המספר הכולל של צמתים יהיה שווה ל:
N = 2I + 1 - אם T מכיל 'N' המספר הכולל של צמתים ו-'I' כדי להיות מספר הצמתים הפנימיים, אז מספר הצמתים הפנימיים יהיה שווה ל:
I = (N-1)/2 - אם ל-'T' יש 'N' המספר הכולל של צמתים, ו-'L' הוא מספר צמתים עלים, אזי מספר צמתי העלים יהיה שווה ל:
L = (N+1)/2 - אם 'T' מכיל מספר 'L' של צמתים עלים, אז המספר הכולל של צמתים יהיה שווה ל:
N = 2L - 1 - אם ל-'T' יש מספר 'L' של צמתים עלים, ו-'I' הוא מספר צמתים פנימיים, אז מספר הצמתים הפנימיים יהיה שווה ל:
I = L - 1
מהו עץ בינארי שלם?
אומרים שעץ בינארי הוא עץ בינארי שלם כאשר כל הרמות מלאות לגמרי מלבד הרמה האחרונה, שמתמלאת משמאל.
העץ שלהלן הוא עץ בינארי שלם:
העץ הבינארי המלא דומה לעץ הבינארי המלא למעט שני ההבדלים המפורטים להלן:
- המילוי של צומת העלה חייב להתחיל מהצד השמאלי ביותר.
- אין זה חובה שלצומת העלה האחרון יהיה האח הנכון.
בואו נבין את הנקודות לעיל באמצעות דוגמה:
שקול את העץ הבא:
העץ שלמעלה הוא עץ בינארי שלם, אך לא עץ בינארי מלא, שכן לצומת 6 אין אחיו הימני.
יצירת עץ בינארי שלם
נניח שיש לנו מערך של 6 אלמנטים המוצגים להלן:
כיצד לשנות מחרוזת ל-int
המערך שלעיל מכיל 6 אלמנטים, כלומר, 1, 2, 3, 4, 5, 6. להלן השלבים שישמשו ליצירת עץ בינארי שלם:
שלב 1: ראשית, נבחר את האלמנט הראשון של המערך, כלומר 1, וניצור צומת שורש של העץ. מספר האלמנטים הזמינים ברמה הראשונה הוא 1.
שלב 2: כעת, נבחר את הרכיב השני והשלישי של המערך. שמור על האלמנט השני והאלמנט השלישי של המערך בתור הילד השמאלי והימני של צומת השורש, בהתאמה המוצגים להלן:
כפי שניתן לראות לעיל, מספר האלמנטים הזמינים ברמה השנייה הוא 2.
שלב 3: כעת, נבחר את שני האלמנטים הבאים מהמערך, כלומר, 4 ו-5. שמור את שני האלמנטים הללו משמאל ומימין של צומת 2 המוצגים להלן:
כפי שאנו יכולים להבחין לעיל שהצמתים 4 ו-5 הם הילד השמאלי והימני של צומת 2 בהתאמה.
שלב 4: כעת, נבחר את האלמנט האחרון של המערך, כלומר, 6, ונשמור אותו כילד שמאלי של הצומת 3 מכיוון שאנו יודעים שבעץ בינארי שלם, הצמתים ממולאים מהצד השמאלי שמוצג להלן:
כפי שאנו יכולים לראות שהרמה השנייה מכילה 3 אלמנטים.
בואו נבין את ההבדלים בין עץ בינארי מלא לעץ בינארי מלא דרך התמונות.
- העץ הבינארי שמוצג להלן אינו עץ בינארי שלם או מלא. זה לא עץ בינארי מלא כי לצומת 3 יש רק ילד אחד. זה גם לא עץ בינארי שלם שכן יש למלא את הצמתים מצד שמאל, אבל לצומת 3 יש ילד ימני ואין לו ילד שמאלי.
- העץ הבינארי, שמוצג להלן, הוא עץ בינארי מלא אך לא עץ בינארי שלם. זהו עץ בינארי מלא מכיוון שלכל הצמתים יש 0 או 2 ילדים. זה לא עץ בינארי שלם כי לצומת 3 אין ילדים ואילו לצומת 2 יש ילדים ואנו יודעים שצריך למלא את הצמתים מצד שמאל בעץ בינארי שלם.
- העץ הבינארי שמוצג להלן הוא עץ בינארי שלם אך לא עץ בינארי מלא. זהו עץ בינארי שלם שכן כל הצמתים נותרים מלאים. זה לא עץ בינארי מלא שכן לצומת 2 יש רק ילד אחד.
- העץ הבינארי שמוצג להלן הוא עץ בינארי שלם כמו גם עץ בינארי מלא. זהו עץ בינארי שלם שכן כל הצמתים נותרים מלאים. זהו עץ בינארי מלא מכיוון שלכל הצמתים יש 0 או 2 ילדים.
