בכיתה
(הערה: הפוסט מוכן לגמרי)
1. פתרון משותף של הבוחן מ- 3.2.22
א. ניתוח טיפוס ייחוס מול טיפוס עצם.
ב. תזכורת לטענת כניסה ויציאה.
ג. המרה מרומזת.
ד. גישה חיצונית לתכונה בעלת הרשת-גישה private או protected.
ה. משתנה סטטי במחלקה.
ו. מתי כותבים this ללא נקודה אחריו?
ז. בנאי המזמן מפורשות בנאי של מחלקת אב.
ח. כיצד נאפשר גישה לתכונה בעלת הרשאת-גישה private.
2. הסברים / דגשים לפתרונות תרגילי הבית שניתנו להיום בנושא עצים
דוגמה פתורה 2: מספר צמתים בעץ ** NumNodes (עמ' 169 בספר)
הסבר: תנאי העצירה של הרקורסיה שואל (if(t==0 ואם כן: return 0.
הסיבה לכך היא שכאשר סריקת העץ מגיעה לבן (שמאלי או ימני) שהוא null,
הרי שאין טעם לספור אותו, ולכן יוחזר 0.
אחרת, אם קיים צומת (כל צומת קיים מכיל ערך שלם כלשהו), נחזיר 1.
בשורת הזימון הרקורסיבי בתרגיל זה:
;return NumNodes(t.GetLeft()) + NumNodes(t.GetRight()) + 1
ניתן לראות בשורה זו שקיימים בה שני זימונים רקורסיביים.
הסיבה היא שעבור כל צומת נרצה לבדוק אם יש לו בן שמאלי (נוסף 1) או
בן ימני (גם כן נוסיף 1), כאשר אין בן - יוחזר 0, כי כאשר אין בן,
תנאי העצירה מחזיר 0.
דוגמה: אם לעץ שורש (עם הערך 5) ובן שמאלי אחד בלבד (עם הערך 3):
שליחת העץ t לפעולה
שורת הקוד של תנאי העצירה *לא-מתקיימת* (כי הצומת 5 אינו null),
ולכן עוברים לשורת ה- return:
זימון רקורסיבי של הפעולה על הבן השמאלי (העץ השמאלי)
מתבצע זימון רקורסיבי של הבן השמאלי (3).
שורת הקוד של תנאי העצירה שוב *לא-מתקיימת* (כי הצומת 3 אינו null),
ולכן עוברים לשורת ה- return: מתבצע זימון רקורסיבי של הבן השמאלי (של 3),
שורת הקוד של תנאי העצירה תחזיר 0.
נתמקד בנקודה הספציפית הנוכחית בה נמצאת כרגע הפעולה
;return 0 + NumNodes(t.GetRight()) + 1
דיון: הסיבה שמוחזר 0 היא כי הזימון הרקורסיבי האחרון של NumNodes
היה על הבן השמאלי של 3, שזה null, ולכן הוחזר 0.
שאלה: האם שורת הקוד הנוכחית
;return 0 + NumNodes(t.GetRight()) + 1
תחזיר 0 ?
תשובה: לא. כיוון ששורת הקוד עדיין לא הגיעה לסופה, ל- ' ; '.
מה קורה עכשיו? עכשיו מתבצע הזימון השני בשורת הקוד:
(NumNodes(t.GetRight)
מתבצע זימון רקורסיבי של הבן הימני (של 3),
גם זימון זה יחזיר 0, כיוון שאין ל- 3 בן ימני.
נתמקד בנקודה הספציפית הנוכחית בה נמצאת כרגע הפעולה
;return 0 + 0 + 1, כלומר: מוחזר הערך 1.
סיימנו לעבור על הצומת 3, והוא החזיר 1.
לאן מוחזר הערך 1?
לקוד שזימן את הפעולה הרקורסיבית על הצומת 3:
סריקת הקוד חוזרת לצומת 5, כיוון שהסתיימה הסריקה של צד שמאל של 5.
נתמקד בנקודה הספציפית הנוכחית בה נמצאת כרגע הפעולה
;return 1 + NumNodes(t.GetRight()) + 1
הערך 1 חזר כתוצאה מהזימון הרקורסיבי הראשון בשורת הקוד:
כעת יוחזר הערך מהחלק הימני של שורת הקוד:
NumNodes(t.GetRight())
ברור לנו שיוחזר 0, כיוון שאין בן ימני ל- 5, ולכן שורת הקוד תיראה כך:
1+0+1
לסיכום: הפעולה הרקורסיבית החזירה את הערך 2 (ובאמת היו בעץ שני צמתים: 5 ו- 3).
זכרו שכל זימון רקורסיבי פותח עותק חדש בזיכרון של הפעולה.
הסבר: באופן דומה לדוגמה פתורה2, גם כאן קיימים שני זימונים רקורסיביים,
מופיע כאן פעמיים הסימן 'או' - ' || ' (סה"כ 3 חלקים לקוד השורה return).
המשמעות היא שמספיק שאחד משלושת חלקי שורת ה- return מחזיר true,
הפעולה כולה מחזירה true.
3. קישור לסרטון
למי שרוצה: כאן.
לבית
1. חקר פתרון הבוחן - שאלות 1-6 (הראשונות)
השאלות כאן, הפתרונות כאן.
2. תרגול
בצעו את החלק השני של הבוחן: ("שאלות Ran") 1-6.
הקישור לשאלות - בסעיף הקודם או כאן.
3. תרגילי השלמת שורות קוד בעצים
דף תרגילי עצים - השלמת שורות, חלק א' כאן
4. בוחן יהלום נוסף
בשבועות הקרובים יינתן שוב בוחן היהלום (אותו הבוחן שפתרנו היום בכיתה).
זמן: 20 דק'. וודאו שאתם יודעים לענות עליו בזמן זה.
בשיעורים הבאים
1. תרגיל2, עמ' 116 - "מעקב" (מתוך הספר של מבט לחלונות).
2. תרגיל3, עמ' 118 - "ניתוח תיעוד ומעקב" (מתוך הספר של מבט לחלונות).
3. עצים: המחלקה <BinNode<T וניתוח הממשק שלה (ע' 162-168).
4. תרגיל בגרות נוסף (שאלה בנושא הורשה