תרגילי חזרה לבגרות – מדעי המחשב
שאלה 1
נתונה מחסנית לא ריקה של עצים לא ריקים בגובה n>1 כך שבכל עץ יש ערכי תווים מסוג char.
כתוב פעולה שמקבלת מחסנית של עצים ובודקת אם כל העצים במחסנית מקיימים את התנאי שיש בהם "מסלול a" אם כן הפעולה תחזיר אמת, אחרת הפעולה תחזיר שקר.
"מסלול a" הוא מסלול המתחיל בשורש העץ, ומסתיים באחד העלים שלו וכל ערכי הצמתים בו שווים לאות ‘a’.
דוגמאות:
בדוגמאות הנ"ל בעץ t1 אין "מסלול a" ובעץ t2 יש "מסלול a"
כותרת הפעולה היא:
public static boolean isAllTreesWithARoute(Stack<BinNode<Character>> st)
שימו לב: בסוף הפעולה על המחסנית להישאר ללא שינוי
תשובה לשאלה 1
נבנה פעולה עזר שמקבלת מצביע לשורש של עץ, ומחזירה true אם יש "מסלול a"
public static boolean isARouteInTree(BinNode<Character> t){
if (!t.hasLeft() && !t.hasRight())
return (t.getValue() == 'a');
else if (t.hasLeft() && !t.hasRight())
return t.getValue() == 'a' && isARouteInTree(t.getLeft());
else if (!t.hasLeft() && t.hasRight())
return t.getValue() == 'a' && isARouteInTree(t.getRight());
else
return t.getValue() == 'a' && (isARouteInTree(t.getRight()) ||
isARouteInTree(t.getLeft()));
}
ועכשיו נשתמש בפעולת העזר בפעולה הראשית שלנו
public static boolean isAllTreesWithARoute(Stack<BinNode<Character>> st){
Stack<BinNode<Character>> tmp = new Stack<BinNode<Character>>();
BinNode<Character> tree;
boolean flag = true;
while (st.isEmpty()){
tmp.push(st.pop());
tree = tmp.top();
flag = flag & isARouteInTree(tree);
}
while (!tmp.isEmpty())
st.push(tmp.pop());
return flag;
}
שאלה 2
כתוב פעולה המקבלת מספר טבעי N ובונה עץ בעל N רמות כך שכל רמה בעץ היא מלאה וכל ערכי הצמתים בכל רמה הם כמספר הרמה.
דוגמה: עבור N = 2 הפעולה תחזיר את העץ הבא
תשובה לשאלה 2
נבנה פעולת עזר שמקבלת עץ לא ריק t , ומספר num ומוסיפה לכל העלים בעץ שני בנים עם הערך num
public static void insertLevelToTree(BinNode<Integer> t,int num){
if (t == null)
return;
else if (!t.hasLeft() && !t.hasRight()){
t.setLeft(new BinNode<Integer>(num));
t.setRight(new BinNode<Integer>(num));
}
else{
insertLevelToTree(t.getLeft(), num);
insertLevelToTree(t.getRight(),num);
}
}
והפעולה הראשית שנתבקשנו לבנות:
public static BinNode<Integer> fillLevelTree(int level){
BinNode <Integer> tree = new BinNode<Integer>(0);
for (int i=1;i<=level;i++)
insertLevelToTree(tree, i);
return tree;
}