ex6a2 עצים בינאריים BinNode

6a2.1 בדיקת ערכים אי-זוגיים בעץ בינארי

עליכם לממש פונקציה חיצונית בשם AllValuesAreOdd אשר מקבלת פרמטר אחד:

1. t - עץ בינארי (מסוג BinNode) שהצמתים שלו הם מטיפוס שלם.

הפונקציה צריכה להחזיר true אם העץ מכיל אך ורק ערכים אי-זוגיים, ו-false אם הוא מכיל לפחות ערך זוגי אחד.

דגשים:

1. השתמשו ברקורסיה כדי לעבור על כל צומתי העץ.
2. בדקו כל ערך בצומת: אם הוא זוגי, החזירו false מיד.
3. אם הגעתם לסוף ענף (צומת null) מבלי למצוא ערך זוגי, המשמעות היא שהענף הזה מכיל רק ערכים אי-זוגיים (או שהוא ריק).
4. זכרו לכלול את ה-using המתאים עבור Unit4.CollectionsLib ו-Unit4.BinTreeUtilsLib.

דוגמאות:

1. עבור העץ:

1 /
3 5 הפונקציה תחזיר: true

1. עבור העץ:

1 /
2 5 הפונקציה תחזיר: false (בגלל הערך 2)

1. עבור העץ:

7 /
9 11 /
13 15 הפונקציה תחזיר: true

6a2.2. בדיקת זוגות אחים בעץ בינארי

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

המשימה שלכם היא לכתוב פונקציה בשפת C# בשם HasIdenticalSiblings. הפונקציה תקבל כפרמטר את השורש של עץ בינארי המכיל מספרים שלמים.

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

• אם נמצא זוג כזה של אחים עם ערכים זהים, הפונקציה צריכה להחזיר true.
• אם לא נמצא אף זוג כזה בכל העץ, הפונקציה צריכה להחזיר false.

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

קלט

הפונקציה תקבל עצם מסוג BinNode של Unit4 המייצג את שורש העץ הבינארי.

פלט

הפונקציה תחזיר ערך בוליאני (bool): true אם נמצאו אחים בעלי ערך זהה, ו-false אחרת. הפונקציה לא תדפיס דבר.

דוגמאות

קלט: Tree: 10 /
/
5 5 / \ /
1 2 3 4 פלט : true

קלט: Tree: 10 /
/
5 8 / \ /
1 2 3 4 פלט : false

קלט: Tree: 10 /
/
5 6 / \ /
1 1 3 4 פלט : true

קלט: Tree: 10 /
/
5 6 פלט : false

קלט: Tree: 10 פלט : false

קלט: Tree: null פלט : false

6a2.3. בדיקת ערך עלים מול ערך אב בעץ בינארי

עליכם לממש פונקציה חיצונית בשם AreLeavesEqualToParent אשר מקבלת פרמטר אחד:

1. t - עץ בינארי (מסוג BinNode) שצמתיו הם מטיפוס מספר שלם.

הפונקציה צריכה להחזיר true אם ערכם של כל העלים בעץ זהה לערך של אביהם, ו-false אם לא.

הנחיות:

1. עליכם להשתמש בפונקציית עזר (helper function) רקורסיבית שתעבור על העץ.
2. פונקציית העזר צריכה לקבל את הצומת הנוכחי ואת ערך האב של הצומת הנוכחי.
3. אם הצומת הוא עלה (אין לו ילד שמאלי ואין לו ילד ימני), בדקו האם ערכו שווה לערך האב שהועבר לפונקציה.
4. אם הצומת אינו עלה, קראו באופן רקורסיבי עבור ילדיו, כאשר ערך האב עבור הילדים הוא ערך הצומת הנוכחי.
5. שימו לב למקרה של עץ ריק או עץ עם צומת בודד (שהוא גם עלה וגם שורש) - במקרים אלו, התנאי נחשב כמתקיים.

שימוש במחלקות:

לצורך פתרון התרגיל, עליכם להשתמש ב-BinNode מהספרייה Unit4.CollectionsLib. יש להוסיף את השורה using Unit4.CollectionsLib; בתחילת הקובץ.

דוגמאות:

1. עץ שבו כל עלה שווה לערך אביו:

10

/ \

5 10

/ \ /

5 5 10

הפונקציה תחזיר: true

1. עץ שבו עלה אחד אינו שווה לערך אביו:

10

/ \

5 10

/ \ /

5 6 10

הפונקציה תחזיר: false

1. עץ עם עלה בודד שהוא גם השורש (אין לו אב):

7

הפונקציה תחזיר: true (אין עלים שאינם השורש, ולכן התנאי מתקיים באופן טריוויאלי).

1. עץ ריק:

null

הפונקציה תחזיר: true (אין עלים לבדוק).

6a2.4. עץ אריאל

עליכם לממש פונקציה חיצונית בשם IsArielTree אשר מקבלת פרמטר אחד:

1. t - עץ בינארי (מסוג BinNode) שהצמתים שלו הם מטיפוס שלם.

הפונקציה צריכה להחזיר true אם העץ הנתון הוא ‘עץ אריאל’, ו-false אם לא.

הגדרת ‘עץ אריאל’

‘עץ אריאל’ מוגדר באופן רקורסיבי כך:

1. עלה (צומת ללא בנים) הוא ‘עץ אריאל’.
2. עץ ששני בניו (הבן השמאלי והבן הימני) הם בעצמם ‘עצי אריאל’ הוא גם ‘עץ אריאל’.

דרישות

1. הפונקציה חייבת להיות חיצונית (לא מתודה של המחלקה BinNode).
2. השתמשו במחלקת BinNode עבור העץ הבינארי.

שימו לב

1. עץ שיש לו רק בן אחד (שמאלי או ימני) אינו עץ אריאל (אלא אם כן הוא עלה).

לצורך פתרון התרגיל, עליכם להשתמש ב:

using Unit4.CollectionsLib;

6a2.5 בדיקת צומת עם בנים שונים בעץ בינארי

עליכם לממש פונקציה חיצונית בשם IsArielTree אשר מקבלת פרמטר אחד:

1. t - עץ בינארי (מסוג BinNode) שהצמתים שלו הם מטיפוס שלם.

הפונקציה צריכה להחזיר true אם העץ הנתון הוא ‘עץ אריאל’, ו-false אם לא.

הגדרת ‘עץ אריאל’

‘עץ אריאל’ מוגדר באופן רקורסיבי כך:

1. עלה (צומת ללא בנים) הוא ‘עץ אריאל’.
2. עץ ששני בניו (הבן השמאלי והבן הימני) הם בעצמם ‘עצי אריאל’ הוא גם ‘עץ אריאל’.

דרישות

1. הפונקציה חייבת להיות חיצונית (לא מתודה של המחלקה BinNode).
2. השתמשו במחלקת BinNode עבור העץ הבינארי.

שימו לב

1. עץ שיש לו רק בן אחד (שמאלי או ימני) אינו עץ אריאל (אלא אם כן הוא עלה).

לצורך פתרון התרגיל, עליכם להשתמש ב:

using Unit4.CollectionsLib;

6a2.6 עץ יחיאל

עליכם לממש פונקציה חיצונית בשם IsYechielTree אשר מקבלת פרמטר אחד:

1. BinNode(t)

הפונקציה צריכה להחזיר true אם העץ הוא ‘עץ יחיאל’, ו-false אחרת.

הגדרת ‘עץ יחיאל’:

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

דגשים:

1. השתמשו בגישה רקורסיבית לפתרון הבעיה.
2. יש לטפל במקרים שבהם לצומת יש רק בן שמאלי או רק בן ימני.

6a2.7. עץ צחי

עליכם לממש פונקציה חיצונית בשם IsTzachiTree אשר מקבלת פרמטר אחד:

1. t - עץ בינארי (BinNode

הפונקציה צריכה להחזיר true אם העץ הינו עץ צחי, ו-false אם לא.

הגדרת עץ צחי

עץ בינארי יקרא “צחי” אם מתקיים אחד מהתנאים הבאים:

1. העץ הוא עלה (כלומר, אין לו בנים).
2. ערכו של העץ זהה לערכו של לפחות אחד מבניו, ואותו בן הינו עץ צחי בעצמו.

דגשים

1. השתמשו ברקורסיה כדי לפתור את הבעיה.
2. עליכם להשתמש במחלקת BinNode עבור העץ הבינארי. יש לייבא את המחלקה באמצעות using Unit4.CollectionsLib;.

6a2.8. בדיקת עץ בינארי מיוחד

עליכם לממש פונקציה חיצונית בשם CheckSpecialBinaryTree אשר מקבלת פרמטר אחד:

1. t - עץ בינארי מטיפוס BinNode

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

1. הערך של צומת ימני קטן מהערך של אביו.
2. הערך של צומת שמאלי גדול מהערך של אביו.

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

דגשים

1. השתמשו במחלקה BinNode.
2. הפונקציה צריכה להיות חיצונית (לא חלק ממחלקת BinNode).
3. עליכם לטפל במקרה של עץ ריק (null).
4. השתמשו בשיטה רקורסיבית לפתרון הבעיה.

6a2.9. בדיקת עץ מעיין

עליכם לממש פעולה חיצונית (פונקציה סטטית) בשם IsMaayanTree אשר מקבלת פרמטר אחד:

1. T - עץ בינארי (BinNode

הפעולה צריכה להחזיר true אם העץ הינו ‘עץ מעיין’, וfalse אם לא.

הגדרת ‘עץ מעיין’

עץ בינארי ייקרא ‘עץ מעיין’ אם לכל צומת בעץ שיש לו נכד (כלומר, צומת שנמצא במרחק של שני קשרים או יותר מהצומת הנוכחי), יש לו בן יחיד (כלומר, או רק בן ימני או רק בן שמאלי, אך לא שניהם).

דגשים למימוש:

1. הפונקציה צריכה לבדוק את התנאי באופן רקורסיבי או איטרטיבי על כל הצמתים בעץ.
2. שימו לב למקרי קצה של צמתים ללא בנים או עם בן אחד בלבד.
3. אם צומת כלשהו מפר את התנאי, הפונקציה צריכה להחזיר false מיד.
4. אם כל הצמתים מקיימים את התנאי, הפונקציה תחזיר true.

שימוש במחלקות עזר:

לצורך פתרון התרגיל, עליכם להשתמש במחלקות BinNode מתוך Unit4.CollectionsLib.

6a2.111