שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2020 - עצים בינאריים

נניח שהמחלקה `Node` שלהלן מממשת עץ בינרי. ```java public class Node { private int _number; private Node _leftSon, _rightSon; public Node (int number) { _number = number; _leftSon = null; _rightSon = null; } public int getNumber() { return _number; } public Node getLeftSon() { return _leftSon; } public Node getRightSon() { return _rightSon; } } ``` המחלקה `BinaryTree` מאגדת בתוכה שיטות סטטיות לטיפול בעץ בינרי. בין השיטות נתונות השיטות `what` ו- `secret` הבאות: ```java public static int what (Node t) { if (t == null) return 0; return 1 + Math.max (what (t.getLeftSon()), what (t.getRightSon())); } public static void secret(Node node, int[] a) { secret (node, 0, a); } private static void secret (Node node, int k, int[] a) { if (node == null) return; a[k] += node.getNumber(); secret (node.getLeftSon(), k + 1, a); secret (node.getRightSon(), k + 1, a); } ``` נניח שקיימת במחלקה `BinaryTree` גם השיטה `printArr` הבאה, המדפיסה את הערכים שבתאי מערך חד-ממדי הניתן לה כפרמטר: ```java public static void printArr(int arr[], int n) { for (int i = 0; i < n; i++) System.out.print(arr[i]+ " " ); System.out.println(); } ``` נתון העץ הבינרי הבא, ששורשו הוא `root` ענו על הסעיפים הבאים: (2 נק') (א) איזה ערך תחזיר השיטה `what` בעקבות הקריאה `BinaryTree.what(root)`? (3 נק') (ב) מה מבצעת השיטה `what` באופן כללי כשהיא מקבלת כפרמטר שורש של עץ בינרי `root`? שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. כלומר, מה המשמעות של הערך שהשיטה מחזירה? (5 נק') (ג) מה יודפס כתוצאה מביצוע קטע הקוד הבא, כאשר `root` הוא שורש העץ לעיל: ```java int num = what(root); int [] a = new int[num]; secret(root, a); printArr(a, num); ``` (7 נק') (ד) מה מבצעת השיטה `secret` באופן כללי כשהיא מקבלת כפרמטר שורש של עץ בינרי `root`, ומערך $a$ ? שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. כתבו מה המשמעות של הערכים שמודפסים לאחר הפקודה `printArr(a, num)`

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

פתרון: מאחר ושרטוט העץ חסר בשאלה, נניח לצורך הפתרון שהעץ הנתון הוא כזה ששורשו (`root`) הוא 4, בנו השמאלי הוא 2, בנו הימני הוא 6. לבן השמאלי (2) יש שני בנים: 1 (שמאלי) ו-3 (ימני). לבן הימני (6) יש בן שמאלי 5, ובן ימני null. **(א)** השיטה `what` מבצעת קריאה רקורסיבית על תת-העץ השמאלי ועל תת-העץ הימני, ומוסיפה 1 למקסימום בין הערכים המוחזרים. מקרה הבסיס הוא עץ ריק (`null`), שעבורו מוחזר 0. זהו חישוב רקורסיבי של **גובה העץ** (כאשר גובה מוגדר כמספר הצמתים במסלול הארוך ביותר מהשורש לעלה). נבצע מעקב אחר הקריאה `BinaryTree.what(root)`: 1. `what(4)` -> `1 + max(what(2), what(6))` 2. `what(2)` -> `1 + max(what(1), what(3))` 3. `what(1)` -> `1 + max(what(null), what(null))` -> `1 + max(0, 0)` -> `1` 4. `what(3)` -> `1 + max(what(null), what(null))` -> `1 + max(0, 0)` -> `1` 5. לכן, `what(2)` -> `1 + max(1, 1)` -> `2` 6. `what(6)` -> `1 + max(what(5), what(null))` 7. `what(5)` -> `1 + max(what(null), what(null))` -> `1 + max(0, 0)` -> `1` 8. `what(null)` -> `0` 9. לכן, `what(6)` -> `1 + max(1, 0)` -> `2` 10. לבסוף, `what(4)` -> `1 + max(2, 2)` -> `3` הערך שיוחזר הוא **3**. **(ב)** באופן כללי, השיטה `what` מחשבת ומחזירה את **הגובה** של העץ הבינארי ששורשו ניתן כפרמטר. **גובה של עץ** מוגדר כמספר הצמתים במסלול הארוך ביותר מהשורש ועד לעלה הרחוק ביותר. עבור עץ ריק, השיטה מחזירה 0, בהתאם להגדרה המקובלת שגובה עץ ריק הוא 0. **(ג)** קטע הקוד מבצע את הפעולות הבאות: 1. `int num = what(root);` : כפי שחישבנו בסעיף א', `num` יקבל את הערך 3. 2. `int [] a = new int[num];` : נוצר מערך `a` בגודל 3, שמאותחל לערכים `{0, 0, 0}`. 3. `secret(root, a);` : נקראת השיטה `secret` עם שורש העץ והמערך `a`. זוהי קריאה לשיטת העטיפה (wrapper) הציבורית, אשר קוראת לשיטה הרקורסיבית הפרטית עם עומק התחלתי `k=0`: `secret(root, 0, a)`. נעקוב אחר ביצוע השיטה `secret(node, k, a)`: השיטה מבצעת סריקת **קדם-סדר (pre-order)** של העץ. הפרמטר `k` מייצג את עומק הצומת הנוכחי בעץ (כאשר עומק השורש הוא 0). בכל קריאה, השיטה מוסיפה את ערך הצומת הנוכחי לתא במערך `a` שאינדקסו הוא עומק הצומת (`a[k]`). - `secret(4, 0, a)`: `a[0] += 4`. המערך: `{4, 0, 0}`. קוראת ל-`secret(2, 1, a)` ו-`secret(6, 1, a)`. - `secret(2, 1, a)`: `a[1] += 2`. המערך: `{4, 2, 0}`. קוראת ל-`secret(1, 2, a)` ו-`secret(3, 2, a)`. - `secret(1, 2, a)`: `a[2] += 1`. המערך: `{4, 2, 1}`. חוזרת. - `secret(3, 2, a)`: `a[2] += 3`. המערך: `{4, 2, 4}`. חוזרת. - `secret(6, 1, a)`: `a[1] += 6`. המערך: `{4, 8, 4}`. קוראת ל-`secret(5, 2, a)` ו-`secret(null, 2, a)`. - `secret(5, 2, a)`: `a[2] += 5`. המערך: `{4, 8, 9}`. חוזרת. - `secret(null, 2, a)`: חוזרת. בסיום ריצת `secret`, המערך `a` יכיל את הערכים `{4, 8, 9}`. 4. `printArr(a, num);` : השיטה מדפיסה את `num=3` האיברים הראשונים של `a`. הפלט שיתקבל הוא: **`4 8 9`** **(ד)** באופן כללי, השיטה `secret` מקבלת שורש של עץ בינארי `root` ומערך `a`. היא מבצעת **סריקה רקורסיבית של העץ** ו**מסכמת את ערכי הצמתים בכל רמה (level) של העץ**. התוצאה נשמרת במערך `a`. ספציפית, בתא `a[i]` יצטבר סכום הערכים של כל הצמתים הנמצאים ברמה `i` של העץ (כאשר רמת השורש היא 0). בקטע הקוד הנתון, המערך `a` נוצר בגודל המתאים בדיוק לגובה העץ (כפי שמחושב על ידי `what`). לכן, לאחר ביצוע הפקודה `secret(root, a)`, המערך `a` יכיל את סכומי הרמות של העץ. הפקודה `printArr(a, num)` מדפיסה את הערכים הללו, כלומר את **סכום ערכי הצמתים עבור כל רמה בעץ, מהרמה 0 (השורש) ועד לרמה העמוקה ביותר**.