→ חזרו אחורה

פרק 14 - עצים בינריים (BinNode)

⏱ 16 דקות קריאה

ב-Node כל צומת הצביע על צומת אחד בלבד אחריו - שרשרת ליניארית. BinNode (Binary Node) שובר את הקו הישר: לכל צומת יש עד שני צאצאים, "שמאלי" ו"ימני". המבנה שנוצר נקרא עץ בינרי, וכל פעולה עליו כמעט תמיד כתובה בעזרת רקורסיה (פרק 10).

1. מחלקת BinNode - החתימה הסטנדרטית

⁦C#⁩

public class BinNode<T> {
    private T value;
    private BinNode<T> left;
    private BinNode<T> right;

    public BinNode(T value) { ... }                                   // עלה - בלי ילדים
    public BinNode(BinNode<T> left, T value, BinNode<T> right) { ... }

    public T GetValue() { ... }
    public BinNode<T> GetLeft() { ... }
    public BinNode<T> GetRight() { ... }
    public bool HasLeft() { ... }
    public bool HasRight() { ... }
}

צומת בלי ילדים בכלל (HasLeft() ו-HasRight() שניהם false) נקרא עלה (leaf). בדיוק כמו ב-Node, תמיד בודקים HasLeft()/HasRight() לפני קריאה ל-GetLeft()/GetRight() - קריאה לצאצא שלא קיים מחזירה null.

2. בניית עץ קטן

⁦C#⁩

BinNode<int> leftLeaf = new BinNode<int>(4);
BinNode<int> rightLeaf = new BinNode<int>(9);
BinNode<int> root = new BinNode<int>(leftLeaf, 7, rightLeaf);

//         7
//        / \
//       4   9

3. מעבר רקורסיבי - ספירת צמתים

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

⁦C#⁩

public static int CountNodes(BinNode<int> node) {
    int count = 1;                              // הצומת הנוכחי עצמו
    if (node.HasLeft()) {
        count += CountNodes(node.GetLeft());
    }
    if (node.HasRight()) {
        count += CountNodes(node.GetRight());
    }
    return count;
}

עבור העץ מסעיף 2: CountNodes(root) מתחילה עם count = 1 (עבור 7), מוסיפה CountNodes(leftLeaf) שמחזירה 1 (ל-4, שהוא עלה), ומוסיפה CountNodes(rightLeaf) שמחזירה 1 (ל-9) - סה"כ 3. שימו לב: אין כאן if נפרד לעלה - עלה פשוט מדלג על שתי הקריאות הרקורסיביות כי HasLeft() ו-HasRight() שלו הן false.

4. טעויות נפוצות

קריאה ל-GetLeft/GetRight בלי בדיקה: קריאה ל-node.GetLeft() כשאין ל-node ילד שמאלי מחזירה null, וקריאה רקורסיבית על null תגרום ל-NullReferenceException.

שכחת אחד הצדדים: טיפול רק ב-HasLeft() בלי הטיפול המקביל ב- HasRight() (או להפך) - מדלג על חצי מהעץ.

בלבול בין הפרמטר הראשון לשלישי בבנאי: בבנאי BinNode(left, value, right) הסדר קבוע - שמאל, ערך, ימין.

🎓 זווית הבגרות

איך זה מופיע בבגרות: BinNode הוא הנושא המתקדם ביותר בחלק א' של שאלון 899271 - כמעט תמיד שאלה שדורשת כתיבת פונקציה רקורסיבית שעוברת על העץ ומחשבת/סוכמת/סופרת משהו.

סוג שאלה טיפוסי: פונקציה רקורסיבית עם תנאי עצירה מרומז (עלה - שתי הקריאות הרקורסיביות פשוט מדולגות כי HasLeft/HasRight הן false), ושילוב התוצאות משני הצדדים.

טעות נפוצה: קריאה ל-GetLeft()/GetRight() בלי לבדוק HasLeft()/HasRight() קודם - גורמת ל-NullReferenceException על עלה.

מה לזכור למבחן: בכל פונקציה רקורסיבית על עץ, בדקו HasLeft/HasRight לפני כל קריאה רקורסיבית לצד המתאים - אין תנאי עצירה מפורש כמו ברקורסיה רגילה, הוא "מובנה" בבדיקות האלה.

5. תרגול

תרגול מעבר (traversal) אמיתי על עץ, לא רק ספירה. הפעולה הבאה עוברת שמאל, ואז השורש, ואז ימין (מעבר "בסדר" - in-order):

⁦C#⁩ 
public static void PrintInOrder(BinNode<int> node) {
    if (node.HasLeft()) {
        PrintInOrder(node.GetLeft());
    }
    Console.Write(node.GetValue() + " ");
    if (node.HasRight()) {
        PrintInOrder(node.GetRight());
    }
}

BinNode<int> left = new BinNode<int>(3);
BinNode<int> right = new BinNode<int>(8);
BinNode<int> root = new BinNode<int>(left, 5, right);
PrintInOrder(root);

באיזה סדר יודפסו הערכים (משמאל לימין)? כתבו את שלושת הערכים מופרדים בפסיק ורווח, למשל: 1, 2, 3

מה יודפס למסך על ידי הקוד הבא? (בהנחה שהפעולה CountNodes מוגדרת כמו למעלה)

⁦C#⁩ 
BinNode<int> a = new BinNode<int>(1);
BinNode<int> b = new BinNode<int>(2);
BinNode<int> c = new BinNode<int>(a, 3, b);
BinNode<int> root = new BinNode<int>(c, 4, null);
Console.WriteLine(CountNodes(root));

כתבו את התנאי שבודק אם לצומת node יש ילד שמאלי.

כתבו את הקריאה הרקורסיבית שממשיכה לספור צמתים בתת-העץ הימני של node, בתוך הפעולה CountNodes.

כתבו את שורת הקוד שיוצרת עלה חדש (בלי ילדים) עם הערך 12.

→פרק 13 - תור (Queue) פרק 15 - תכנות מונחה עצמים מתקדם←