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

המחלקה 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 מאגדת בתוכה שיטות סטטיות לטיפול בעץ בינרי. התבוננו בשיטה הבאה: ```java public static boolean f(Node t) { if (t == null) return true; if (t.getLeftSon() == null && t.getRightSon() == null) return true; if (t.getLeftSon() == null) return ((t.getNumber() == t.getRightSon().getNumber()) && f(t.getRightSon())); if (t.getRightSon() == null) return ((t.getNumber() == t.getLeftSon().getNumber()) && f(t.getLeftSon())); return (((t.getNumber() == t.getRightSon().getNumber()) && f(t.getRightSon())) || ((t.getNumber() == t.getLeftSon().getNumber()) && f(t.getLeftSon()))); } ``` בהינתן העץ הבינרי הבא: ``` 8 / \ 4 8 / \ / \ 4 8 5 20 /\ | /\ 4 6 8 14 18 | 5 ``` (1) מה יודפס כתוצאה מהפקודה: `System.out.println(BinaryTree.f(root));`

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

פתרון: נעקוב אחרי f(root) כאשר root=8: - root=8: יש שני בנים. בודקים: 8==rightSon(8)? **כן**. f(rightSon)? - צומת 8 (ימני): יש שני בנים (5, 20). 8==20? לא. 8==5? לא. שתי האפשרויות נכשלות => **false** - חוזרים ל-root: האפשרות הימנית נכשלה. בודקים שמאל: 8==leftSon(4)? **לא**. - שתי האפשרויות נכשלות => return false || false => **false** יודפס: **false**