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

נתונה השיטה f הבאה שמקבלת כפרמטר את n מטיפוס Node שהוא מצביע לשורש של עץ בינארי. (העץ לא ריק, כלומר n אינו null). העץ מלא במספרים חיוביים בלבד. המחלקה 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; } } ``` השיטה f: ```java public static int f(Node n) { if (n == null) return 0; if ((n.getLeftSon() == null) && (n.getRightSon() == null)) return n.getNumber(); if (n.getRightSon() == null) return (f(n.getLeftSon())); if (n.getLeftSon() == null) return (f(n.getRightSon())); int a = f(n.getLeftSon()); int b = f(n.getRightSon()); if (a > b) return a; return b; } ``` מה מבצעת השיטה f כאשר היא מקבלת כפרמטר את n מטיפוס Node שהוא מצביע לשורש של עץ בינארי? כתבו בקצרה מה מבצעת השיטה (מבחינת המשמעות של הפעולה) ולא כיצד היא מבצעת זאת.

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

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