פתרון השאלות של היום–18.3.2019

תרגילי חזרה לבגרות – מדעי המחשב

 

שאלה 1

נתונה מחסנית לא ריקה של עצים לא ריקים בגובה n>1 כך שבכל עץ יש ערכי תווים מסוג char.

כתוב פעולה שמקבלת מחסנית של עצים ובודקת אם כל העצים במחסנית מקיימים את התנאי שיש בהם "מסלול a" אם כן הפעולה תחזיר אמת, אחרת הפעולה תחזיר שקר.

"מסלול a" הוא מסלול המתחיל בשורש העץ, ומסתיים באחד העלים שלו וכל ערכי הצמתים בו שווים לאות ‘a’.

דוגמאות:

 

clip_image001   clip_image002

clip_image004clip_image006

 

 

 

 

 

 

בדוגמאות הנ"ל בעץ 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 הפעולה תחזיר את העץ הבא

clip_image008

 

 

 

 

 

 

 

 

תשובה לשאלה 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;

}