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

נניח שהמחלקה `Node` שלהלן ממשת עץ בינארי: ```java public class Node { private int _data; private Node _leftSon, _rightSon; public Node(int data) { _data = data; _leftSon = null; _rightSon = null; } public int getData() { return _data; } public Node getLeftSon() { return _leftSon; } public Node getRightSon() { return _rightSon; } } ``` המחלקה `BinaryTree` מאגדת בתוכה שיטות סטטיות לטיפול בעץ בינארי. בין השיטות נתונות השיטות `f` ו-`what` הבאות: ```java public static int f(Node n) { if (n == null) return 0; return (n.getData() + f(n.getLeftSon()) + f(n.getRightSon())); } public static boolean what(Node n) { if (n == null) return true; if (n.getLeftSon() == null && n.getRightSon() == null) return true; return (n.getData() == (f(n.getLeftSon()) + f(n.getRightSon()))) && what(n.getLeftSon()) && what(n.getRightSon()); } ``` נתון העץ הבינארי הבא, ששורשו הוא `root`: ``` 300 / \ 45 100 / \ 10 25 / / \ 10 15 10 / \ 10 10 ``` (ii) איזה ערך תחזיר השיטה `what` בעקבות הקריאה `BinaryTree.what(root)`?

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

פתרון: השיטה `what` בודקת האם לכל צומת פנימי (שאינו עלה), ערך הצומת שווה לסכום כל הערכים בתת-העץ השמאלי ובתת-העץ הימני שלו. נבדוק עבור השורש (300): - `f(leftSon)` = f(45) = 45 + 10 + 25 + 10 + 15 + 10 + 10 + 10 = **135** - `f(rightSon)` = f(100) = **100** - f(left) + f(right) = 135 + 100 = **235** - 300 != 235 לכן התנאי לא מתקיים כבר בשורש. התשובה היא: **false**