אג 6.3.2020 פעולות עצים מהבגרות

בכיתה
1. שאלה מבגרות תשע"ז 2017 בנושא עצים - Exist
    א. ממשו פעולה חיצונית בשם Exist.
        הפעולה תקבל עץ-בינרי t מטיפוס שלם ומספר שלם x.
        הפעולה תחזיר 'אמת' אם יש בעץ צומת שערכו x, אחרת - 'שקר'.
        אם העץ ריק, הפעולה תחזיר 'שקר'.

public static Node<int> Check(BinNode<int> t1, BinNode<int> t2)

{

        Node<int> first = new Node<int>(-1);

        first = Check(t1, t2, first);

        return first.GetNext();

}

    ב. לפניכם הפעולה (Check(t1, t2
        הפעולה מקבלת שני עצים בינריים לא ריקים מטיפוס שלם t1, t2
        ומחזירה רשימה המכילה את כל המספרים הנמצאים בעץ t1 ואינם נמצאים בעץ t2.
        הפעולה מזמנת פעולה נוספת המקבלת 3 פרמטרים.

        ממשו את הפעולה:

public static Node<int> Check(BinNode<int> t1, BinNode<int> t2, Node<int> list)

{

        ...

}

        תוכלו להשתמש בפעולה שמימשתם בסעיף א'.

    ג. מהי סיבוכיות זמן הריצה של הפעולה שמימשתם בסעיף ב'?

2. שאלה מבגרות תשע"ו 2016 בנושא עצים - UpPath
    עץ מספרים הוא עץ בינרי לא ריק מטיפוס שלם, שהערכים בצמתים שלו
    הם מספרים שלמים וגדולים מ- 0 השונים זה מזה.
    על עץ מספרים מוגדרת פעולה "מסלול-עולה" המחזירה 'אמת' אם יש בעץ
    מסלול המתחיל בשורש העץ ומסתיים באחד העלים שלו, וערכי הצמתים
    ממוינים בסדר עולה מהשורש לעלה. אם אין מסלול כזה, יוחזר 'שקר'.
    לדוגמה:
    בעבור עץ-שלמים tr1 הפעולה "מסלול-עולה" מחזירה 'אמת', המסלול הודגש:

tr1 -->                1

               6                    2

         3        4          17      11

             8            19   12        10

          5

   בעבור עץ-שלמים tr2 הפעולה "מסלול-עולה" מחזירה 'שקר':

tr2 -->

                           1

               6                     2

         3        4           17      11

              8            19   12      10

           5

   ממשו את הפעולה "מסלול-עולה" (UpPath) בעבור עץ מספרים tr.
   כותרת הפעולה:

public static bool UpPath(BinNode<int> tr)

    

לבית
1. בצעו שאלת עצים (מספר 6) מבגרות תשע"ח 2018 - הפעולה TreeLessThanTree
2. בצעו שאלת עצים (מספר 6) מבגרות תשע"ט 2019 - הפעולה Order 

בשיעור הבא
שאלות נוספות מהבגרות בנושא עצים.