בגרות מדעי המחשב 899271, קיץ 2016 מועד א'

לפניכם המחלקה Ring (טבעת) בעלת גודל ("S"/"M"/"L") וצבע, והמחלקה Pole (מוט) המספקת פעולות add (הכנסה לראש המוט, O(1)), remove (הוצאה מהראש, O(1)), isEmpty (O(1)) ו-sort (למימוש). לאחר sort(), הטבעות הגדולות צריכות להיות מונחות בתחתית המוט והקטנות מעליהן.

public class Ring {
    private String size;   // גודל הטבעת ("S"/"M"/"L")
    private int color;     // צבע הטבעת
    public Ring() { this.size = "L"; this.color = 0; }
    public Ring(String str, int c) { this.size = str; this.color = c; }
    public String getSize() { return this.size; }
    public int getColor() { return this.color; }
}

public class Pole {
    private java.util.LinkedList<Ring> data = new java.util.LinkedList<>();
    public Pole() { }
    public void add(Ring r) { data.addFirst(r); }          // O(1) — מכניסה טבעת r לראש המוט
    public Ring remove() { return data.removeFirst(); }     // O(1) — מוציאה ומחזירה את טבעת הראש
    public boolean isEmpty() { return data.isEmpty(); }      // O(1)
    public void sort() {
        // TODO — סעיף א
    }
}

מוגדרת "רשימה דו-כיוונית" כאוסף סדור של חוליות BinNode<Integer> המקושרות כך שלכל זוג חוליות p1,p2: אם p1.getRight()==p2 אז p2.getLeft()==p1 (יש לפחות שתי חוליות). כלומר כל חוליה — חוץ מהחוליה שבקצה הימני והחוליה שבקצה השמאלי — מצביעה על החוליה שלפניה ועל החוליה שלאחריה. בדוגמה שבשאלון: הרשימה 13-10-27-11-8 (null בקצה שמאל, null בקצה ימין), ומשתנה pos מצביע על החוליה עם הערך 11.

public class BinNode<T> {
    private T value;
    private BinNode<T> left;   // ברשימה דו-כיוונית: החוליה השמאלית (הקודמת)
    private BinNode<T> right;  // ברשימה דו-כיוונית: החוליה הימנית (הבאה)
    public BinNode(T value) { this.value = value; this.left = null; this.right = null; }
    public T getValue() { return value; }
    public void setValue(T value) { this.value = value; }
    public BinNode<T> getLeft() { return left; }
    public void setLeft(BinNode<T> left) { this.left = left; }
    public BinNode<T> getRight() { return right; }
    public void setRight(BinNode<T> right) { this.right = right; }
}
// "רשימה דו-כיוונית": לכל זוג חוליות p1,p2 — אם p1.getRight()==p2 אז p2.getLeft()==p1.

הרשימה הדו-כיוונית שבדוגמה, pos מצביע על החוליה עם הערך 11

null <- [13] <-> [10] <-> [27] <-> [11] <-> [8] -> null
                                        ^pos

"עץ מספרים" הוא עץ בינארי לא ריק מטיפוס BinNode<Integer> שהערכים שלו הם מספרים שלמים וגדולים מ-0. על עץ מספרים מוגדרת פעולת "מסלול-עולה": המחזירה true אם יש בעץ מסלול המתחיל בשורש ומסתיים בעלה, ועל-פי ערכי הצמתים ממורש בסדר עולה ממש בהשוואה בין כל שני צמתים סמוכים בו; אם אין מסלול כזה — מחזירה false. בדוגמה: בעבור עץ המספרים tr1 הפעולה "מסלול-עולה" מחזירה true (המסלול מוצף בקו שבור); בעבור עץ המספרים tr2 הפעולה "מסלול-עולה" מחזירה false.

public class BinNode<T> {
    private T value;
    private BinNode<T> left;   // בעץ מספרים: הבן השמאלי
    private BinNode<T> right;  // בעץ מספרים: הבן הימני
    public BinNode(T value) { this.value = value; this.left = null; this.right = null; }
    public T getValue() { return value; }
    public void setValue(T value) { this.value = value; }
    public BinNode<T> getLeft() { return left; }
    public void setLeft(BinNode<T> left) { this.left = left; }
    public BinNode<T> getRight() { return right; }
    public void setRight(BinNode<T> right) { this.right = right; }
}
// כאן BinNode<T> משמש לייצוג עץ בינארי: getLeft/getRight הם הבנים השמאלי/ימני.

tr1 (upPath=true, המסלול 1→2→17→19 מסומן) ו-tr2 (upPath=false)

tr1:                                   tr2:
            1                                       1
         /     \                                 /     \
        6       2*                               6       7
       / \     / \                              / \     / \
      3   4  17* 11                             3   4  14   2
       \      / \   \                            \      / \   \
        8   19* 12  10                             8   9   11  10
       /                                          /
      5                                          5
(* = על המסלול העולה 1->2->17->19, לפי הסימון בשאלון)