העץ הבינארי אומר שלצומת יכולים להיות שני ילדים לכל היותר. כאן, השם הבינארי עצמו מרמז על 'שניים'; לכן, לכל צומת יכולים להיות 0, 1 או 2 ילדים.

בואו נבין את העץ הבינארי באמצעות דוגמה.

העץ שלמעלה הוא עץ בינארי מכיוון שכל צומת מכיל את שני הילדים המרבית. הייצוג הלוגי של העץ לעיל ניתן להלן:

בעץ הנ'ל, צומת 1 מכיל שני מצביעים, כלומר מצביע שמאלה וימינה המצביעים על הצומת השמאלי והימני בהתאמה. הצומת 2 מכיל את שני הצמתים (צומת שמאל וימין); לכן, יש לו שני מצביעים (שמאלה וימין). הצמתים 3, 5 ו-6 הם צמתי העלים, כך שכל הצמתים הללו מכילים ריק מצביע בחלק השמאלי והימני כאחד.

תכונות של עץ בינארי

• בכל רמה של i, המספר המרבי של צמתים הוא 2^אני.
• גובה העץ מוגדר כנתיב הארוך ביותר מצומת השורש לצומת העלה. לעץ שמוצג למעלה יש גובה שווה ל-3. לכן, המספר המרבי של צמתים בגובה 3 שווה ל- (1+2+4+8) = 15. באופן כללי, המספר המרבי של צמתים אפשרי בגובה h הוא (2⁰+ 2¹+ 2²+….2^ח) = 2^h+1-1.
• המספר המינימלי של צמתים אפשרי בגובה h שווה ל h+1 .
• אם מספר הצמתים הוא מינימלי, אז גובה העץ יהיה מקסימלי. לעומת זאת, אם מספר הצמתים הוא מקסימלי, אז גובה העץ יהיה מינימלי.

אם יש מספר 'n' של צמתים בעץ הבינארי.

ניתן לחשב את הגובה המינימלי כך:

כפי שאנו יודעים זאת,

n = 2^h+1-1

n+1 = 2^h+1

לוקחים עץ משני הצדדים,

עֵץ₂(n+1) = log2(2^h+1)

עֵץ₂(n+1) = h+1

h = יומן₂(n+1) - 1

ניתן לחשב את הגובה המרבי כך:

כפי שאנו יודעים זאת,

פרוס מערך java

n = h+1

h=n-1

סוגי עץ בינארי

ישנם ארבעה סוגים של עץ בינארי:

עץ בינארי מלא/ תקין/ קפדני השלם עץ בינארי עץ בינארי מושלם עץ בינארי מנוון עץ בינארי מאוזן

1. עץ בינארי מלא/ תקין/ קפדני

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

בואו נסתכל על הדוגמה הפשוטה של ​​העץ הבינארי המלא.

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

מאפיינים של עץ בינארי מלא

• מספר צמתים עלים שווה למספר הצמתים הפנימיים פלוס 1. בדוגמה לעיל, מספר הצמתים הפנימיים הוא 5; לכן, מספר צמתי העלים שווה ל-6.
• המספר המרבי של צמתים זהה למספר הצמתים בעץ הבינארי, כלומר 2^h+1-1.
• המספר המינימלי של צמתים בעץ הבינארי המלא הוא 2*h-1.
• הגובה המינימלי של העץ הבינארי המלא הוא עֵץ₂(n+1) - 1.
• ניתן לחשב את הגובה המרבי של העץ הבינארי המלא כך:

n=2*h - 1

n+1 = 2*h

h = n+1/2

השלם עץ בינארי

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

בואו ניצור עץ בינארי שלם.

העץ הנ'ל הוא עץ בינארי שלם מכיוון שכל הצמתים מלאים לחלוטין, וכל הצמתים ברמה האחרונה מתווספים תחילה משמאל.

מאפיינים של עץ בינארי שלם

שורה ועמודה

• המספר המרבי של צמתים בעץ בינארי מלא הוא 2^h+1- 1.
• המספר המינימלי של צמתים בעץ בינארי מלא הוא 2^ח.
• הגובה המינימלי של עץ בינארי שלם הוא עֵץ₂(n+1) - 1.
• הגובה המרבי של עץ בינארי שלם הוא

עץ בינארי מושלם

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

בואו נסתכל על דוגמה פשוטה של ​​עץ בינארי מושלם.

העץ שלמטה אינו עץ בינארי מושלם מכיוון שכל צמתי העלים אינם באותה רמה.

הערה: כל העצים הבינאריים המושלמים הם העצים הבינאריים השלמים כמו גם העץ הבינארי המלא, אך להיפך אינו נכון, כלומר, כל העצים הבינאריים השלמים והעצים הבינאריים המלאים הם העצים הבינאריים המושלמים.

עץ בינארי מנוון

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

בואו נבין את העץ הבינארי המנוון באמצעות דוגמאות.

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

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

עץ בינארי מאוזן

העץ הבינארי המאוזן הוא עץ שבו העץ השמאלי והימני נבדלים ב-1 לכל היותר. לדוגמה, AVL ו עצים אדומים-שחורים הם עץ בינארי מאוזן.

בואו נבין את העץ הבינארי המאוזן באמצעות דוגמאות.

העץ שלמעלה הוא עץ בינארי מאוזן מכיוון שההבדל בין תת העץ השמאלי לעץ המשנה הימני הוא אפס.

העץ הנ'ל אינו עץ בינארי מאוזן מכיוון שההבדל בין תת העץ השמאלי לתת העץ הימני גדול מ-1.

יישום עץ בינארי

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

 struct node { int data, struct node *left, *right; } 

במבנה הנ'ל, נתונים הוא הערך, מצביע שמאלי מכיל את הכתובת של הצומת השמאלי, ו מצביע ימני מכיל את הכתובת של הצומת הימני.

תוכנית עץ בינארי ב-C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

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

• מעבר לא-סדר
• מעבר בהזמנה מראש
• העברת הזמנה בדואר