עצים בינאריים מדעי המחשב לכיתה י״ב

בנושא הזה 8 שיעורים. כך הם מתחילים:

1. מושגים והממשק BinNode<T>

   עץ הוא מבנה היררכי: שורש, ילדים, עלים. בשיעור: כל המינוח שבתכנית (שורש, צומת, הורה, ילד, אח, הורה קדמון, צאצא, עלה, מסלול, רמה, גובה, תת-עץ), מהו עץ בינארי, עצים מלאים ועצים "שרוכים", וכתיב הסוגריים שבו נתאר עצים בשאלות.

2. בניית עץ בקוד

   הממשק BinNode<T> (שני בנאים, getValue/getLeft/getRight, hasLeft/hasRight, setValue/setLeft/setRight), בניית עץ מתרשים - מלמטה למעלה או בעזרת set - וקריאת קוד שבונה או משנה עץ.

3. סריקות: תחילית, תוכית וסופית

   שלוש סריקות עומק של עץ בינארי: pre-order (שורש-שמאל-ימין), in-order (שמאל-שורש-ימין), post-order (שמאל-ימין-שורש). המימוש הרקורסיבי, טריק "הקפת העץ" לסריקה מהירה ביד, ושחזור עץ משתי סריקות.

4. פעולות רקורסיביות: ספירה, סכום, גובה

   פעולות רקורסיביות על עצים: מספר צמתים, סכום, מספר עלים, גובה, מקסימום וחיפוש ערך. התבנית: תנאי עצירה על עץ ריק (ולפעמים על עלה), ושילוב התשובות של תת-העץ השמאלי והימני.

5. מעקב אחרי פעולות רקורסיביות

   מעקב אחרי פעולות רקורסיביות על עצים בסגנון הבגרות: "מה תחזיר הפעולה עבור העץ?" ו"מה מבצעת הפעולה באופן כללי?". פעולות עם פרמטר נוסף (רמה), פעולות שמשנות עץ (שיקוף), ופעולה שמשתמשת בפעולה אחרת.

6. סריקה לפי רמות עם תור

   סריקה לרוחב (BFS) של עץ: עוברים רמה אחרי רמה, משמאל לימין, בעזרת תור של צמתים - Queue<BinNode<Integer>>. מעקב אחרי התור, ספירת צמתים ברמה, ההבדל מסריקות העומק.

7. עצי ביטוי ויעילות

   ביטויים חשבוניים בעץ בינארי (עלים = מספרים, צמתים פנימיים = פעולות), חישוב הביטוי ברקורסיה, הקשר בין הסריקות לכתיב תחילי/תוכי/סופי, ויעילות אלגוריתמים על עצים: גובה של עץ מלא מול עץ שרוך.

8. חזרה: עצים בינאריים

   חזרה על עצים בינאריים: מינוח, בנייה, סריקות, פעולות רקורסיביות, מעקב ו"מה מבצעת הפעולה", BFS ועצי ביטוי - בשאלות מעורבות בסגנון שאלת העץ בבגרות.

→ רשימה מקושרתמסלול אלגוריתמים: גרפים ←