דילוג לתוכן המרכזי

סיכום עצים בינריים

מדעי המחשב לבגרות · 3 נושאים

כל מה שצריך לדעת בעצים בינריים: המושגים, הכללים, דרכי פתרון וקוד ב-Java וב-C# עם דוגמאות פתורות משאלוני הבגרות. לחזרה מהירה לפני הבחינה - הסיכום המקוצר או דף כללים.

עץ בינרי

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

בשאלוני 899271 של קיץ 2025 וקיץ 2026, שאלה 3 בפרק הראשון הייתה על עץ בינרי. בשתיהן הפעולות רקורסיביות: כמעט כל מה שעושים בעץ נעשה ברקורסיה.

1. עץ בינרי: המבנה, המינוח והמחלקה BinNode

חוליה בינרית

חוליה בינרית היא כמו חוליה של שרשרת, רק עם שתי הפניות במקום אחת: אחת שמאלה ואחת ימינה. מכמה חוליות כאלה שמחוברות זו לזו מקבלים עץ.
במדויק: עצם מטיפוס BinNode<T> מכיל ערך מטיפוס T ושתי הפניות, left ו-right, לחוליות בינריות אחרות או ל-null. משתנה מטיפוס BinNode מצביע גם על חוליה אחת וגם על כל העץ שמשתרג ממנה: tree.getLeft() הוא הבן השמאלי, והוא גם תת-העץ השמאלי כולו. אין מחלקה Tree: עץ מיוצג רק בעזרת BinNode.

ההשוואה לשרשרת חוליות: ב-Node יש getNext(), וב-BinNode יש getLeft() ו-getRight(). עץ שבו לכל צומת יש לכל היותר בן אחד ("שרוך") הוא בעצם שרשרת.

המינוח של עץ

הדוגמה בטבלה: העץ מקיץ 2026 - השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.

מונחמה זהבעץ הדוגמה
שורשהצומת העליון, שאין לו הורה5
בן (ילד) שמאלי / ימניהצומת שההפניה השמאלית / הימנית מצביעה עליוהבן השמאלי של 1 הוא 0, הימני הוא 7
הורההצומת שמצביע על הבן1 הוא ההורה של 0 ושל 7
אחיםשני בנים של אותו הורה0 ו-7
צאצא / הורה קדמוןכל צומת בתת-העץ של צומת / כל צומת במסלול מהשורש אליו4 צאצא של 1; 5 הורה קדמון של 4
עלהצומת בלי בנים4 ו-3
תת-עץצומת וכל הצאצאים שלותת-העץ של 0: הצמתים 0, 2, 4
מסלולסדרת צמתים שכל אחד מהם בן של הקודם; כל מעבר הוא קשת שמאלית או ימנית5 → 1 → 0 → 2 → 4
רמההמרחק מהשורש בקשתות: השורש ברמה 02 ברמה 3
גובה העץהרמה הגבוהה ביותר: מספר הקשתות במסלול הארוך ביותר מהשורש לעלה4

פעולות הממשק BinNode

מותר להשתמש בהן בלי לממש. כולן O(1).

פעולה (Java)C#מה עושה
BinNode(T x)BinNode(T x)חוליה עם הערך x, שתי ההפניות null
BinNode(BinNode<T> left, T x, BinNode<T> right)אותו דברחוליה עם x ושתי הפניות (כל אחת יכולה להיות null)
getValue()GetValue()ערך החוליה
getLeft() / getRight()GetLeft() / GetRight()הבן השמאלי / הימני, או null
hasLeft() / hasRight()HasLeft() / HasRight()האם יש בן שמאלי / ימני
setValue(x)SetValue(x)משנה את הערך
setLeft(t) / setRight(t)SetLeft(t) / SetRight(t)משנה את ההפניה השמאלית / הימנית
toString()ToString()ערך החוליה כמחרוזת

טיפוס: BinNode<Integer> ב-Java, BinNode<int> ב-C#.

בניית עץ מתרשים

בונים מלמטה למעלה: קודם העלים, ואז כל הורה עם הפעולה הבונה שמקבלת שמאל, ערך וימין. בן שחסר - null. כאן העץ מהטבלה: השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.

public static BinNode<Integer> buildTree()
{
    BinNode<Integer> n4 = new BinNode<Integer>(4);              // עלה
    BinNode<Integer> n2 = new BinNode<Integer>(n4, 2, null);    // רק בן שמאלי
    BinNode<Integer> n0 = new BinNode<Integer>(n2, 0, null);
    BinNode<Integer> n7 = new BinNode<Integer>(null, 7, new BinNode<Integer>(3));
    BinNode<Integer> n1 = new BinNode<Integer>(n0, 1, n7);      // שני בנים
    return new BinNode<Integer>(null, 5, n1);                   // השורש
}

שתי צורות קצה של עץ

צורהאיך נראיתגובה בעץ עם n צמתים
שרוךלכל צומת לכל היותר בן אחד; למשל שרשרת ימנית, שבה לכל צומת חוץ מהאחרון רק בן ימניn − 1: העץ הגבוה ביותר, כמו שרשרת
עץ מלא או כמעט מלאכל הרמות מלאות, חוץ אולי מהאחרונהבערך log n: העץ הנמוך ביותר

בקיץ 2026 שאלו מה הערך הגבוה ביותר ומה הנמוך ביותר ש-foo יכולה להחזיר בעץ עם 6 צמתים: הגבוה ביותר התקבל בשרשרת ימנית, והנמוך ביותר בשרשרת שמאלית - שתיהן עץ "שרוך".

שים לב

לפני t.getLeft().getValue() בודקים t.hasLeft(). לעלה אין בנים, ו-getLeft() מחזיר null: קריאה לפעולה על null היא שגיאה בזמן ריצה.

שים לב

בשאלת ציור קוראים כל מגבלה: מספר הצמתים ("8 צמתים"), מספר הרמות ("מקסימום 4 רמות" = רמות 0 עד 3), והתכונה עצמה ("לכל היותר K קשתות"). אחרי הציור עוברים על כל המסלולים מהשורש לעלים, ובודקים בכל אחד את התכונה.

דוגמה - ציור עץ 1-שמאלי עם 8 צמתים

"עץ K-שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותר K קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים).
בעץ הדוגמה בשאלה: לשורש בן שמאלי ובן ימני; לבן השמאלי רק בן ימני (עלה); לבן הימני בן שמאלי ובן ימני (עלה); לבן השמאלי שלו שני בנים (עלים). במסלול שורש → ימינה → שמאלה → שמאלה יש שתי קשתות שמאליות, ולכן העץ אינו "עץ 1-שמאלי", אבל הוא "עץ 2-שמאלי".
סרטטו "עץ 1-שמאלי" (כלומר שבכל מסלול של העץ יש קשת אחת שמאלית לכל היותר), ובו 8 צמתים ומקסימום 4 רמות.

פתרון
1.המגבלות: 8 צמתים; לכל היותר 4 רמות, כלומר רמות 0 עד 3; בכל מסלול לכל היותר קשת שמאלית אחת.
2.הרעיון: אחרי שיורדים פעם אחת שמאלה, מאותו צומת ממשיכים רק ימינה. מצומת שהגענו אליו רק בקשתות ימניות מותר לרדת שמאלה פעם אחת.
3.העץ (הערכים רק לזיהוי): לשורש 1 - בן שמאלי 2 (עלה) ובן ימני 3. ל-3 - בן שמאלי 4 ובן ימני 5. ל-4 - רק בן ימני 6. ל-5 - בן שמאלי 7 ובן ימני 8.
רמההצמתים
01
12, 3
24, 5
36, 7, 8
4.בדיקה - כל המסלולים מהשורש לעלה:
מסלולקשתות שמאליות
1 → 21
1 → 3 → 4 → 61 (3 → 4)
1 → 3 → 5 → 71 (5 → 7)
1 → 3 → 5 → 80

8 צמתים, 4 רמות, ובכל מסלול לכל היותר קשת שמאלית אחת. ל-4 אסור לתת בן שמאלי: הגענו אליו בקשת שמאלית, ובמסלול היו נוצרות שתיים.

תשובה

לדוגמה: שורש 1; בן שמאלי 2 (עלה), בן ימני 3; ל-3: שמאלי 4, ימני 5; ל-4: ימני 6; ל-5: שמאלי 7, ימני 8. (8 צמתים, 4 רמות, בכל מסלול לכל היותר קשת שמאלית אחת. יש עוד תשובות נכונות.)

2. סריקות של עץ בינרי: תחילית, תוכית וסופית

סריקה של עץ

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

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

שלושת הסדרים על עץ אחד

העץ: השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.

סריקההסדר בכל צומתהפלט
תחילית (pre-order)שורש, שמאל, ימין5 1 0 2 4 7 3
תוכית (in-order)שמאל, שורש, ימין5 4 2 0 1 7 3
סופית (post-order)שמאל, ימין, שורש4 2 0 3 7 1 5
לרוחברמה אחרי רמה5 1 0 7 2 3 4

בתחילית השורש ראשון, ובסופית הוא אחרון. בתוכית 5 ראשון כי אין לו בן שמאלי.

תבנית: שלוש הסריקות לעומק

אותו קוד בשלושתן; משתנה רק המקום של ההדפסה. מקרה הבסיס הוא עץ ריק (null), ולכן אין צורך לבדוק hasLeft() לפני הקריאה.

public static void preOrder(BinNode<Integer> t)    // תחילית
{
    if (t == null)
        return;
    System.out.print(t.getValue() + " ");   // שורש
    preOrder(t.getLeft());                  // שמאל
    preOrder(t.getRight());                 // ימין
}

public static void inOrder(BinNode<Integer> t)     // תוכית
{
    if (t == null)
        return;
    inOrder(t.getLeft());                   // שמאל
    System.out.print(t.getValue() + " ");   // שורש
    inOrder(t.getRight());                  // ימין
}

public static void postOrder(BinNode<Integer> t)   // סופית
{
    if (t == null)
        return;
    postOrder(t.getLeft());                 // שמאל
    postOrder(t.getRight());                // ימין
    System.out.print(t.getValue() + " ");   // שורש
}

תבנית: סריקה לרוחב בעזרת תור

מכניסים את השורש לתור. כל עוד התור לא ריק: מוציאים צומת, מטפלים בו, ומכניסים את הבנים שלו - שמאלי ואז ימני. התור שומר על הסדר של הרמות. על העץ שבטבלה יודפס 5 1 0 7 2 3 4.

public static void levelOrder(BinNode<Integer> root)   // סריקה לרוחב
{
    if (root == null)
        return;
    Queue<BinNode<Integer>> q = new Queue<BinNode<Integer>>();
    q.insert(root);
    while (!q.isEmpty())
    {
        BinNode<Integer> t = q.remove();
        System.out.print(t.getValue() + " ");
        if (t.hasLeft())
            q.insert(t.getLeft());
        if (t.hasRight())
            q.insert(t.getRight());
    }
}
דרך הפתרון

מעקב אחר פעולה רקורסיבית על עץ

1.מסמנים את הצמתים לפי הערכים שבתרשים: foo(5) היא הקריאה על הצומת שערכו 5.
2.טבלה, שורה לכל קריאה: קריאה | מצב הצומת (עלה, רק בן שמאלי, רק בן ימני, שני בנים) | החישוב לפי הקוד | ערך מוחזר.
3.סדר השורות הוא סדר הקריאות: הצומת, אחר כך כל תת-העץ השמאלי, ואחר כך הימני (סדר תחילי).
4.ממלאים את הערכים המוחזרים מלמטה למעלה: קודם העלים, ואז כל הורה לפי הערכים של הבנים שלו.
5.כותבים במפורש את הערך שהקריאה הראשונה מחזירה.
שים לב

ב-goo(tree.getLeft()) && goo(tree.getRight()): אם הקריאה השמאלית מחזירה false, הקריאה הימנית לא מתבצעת בכלל. בטבלת המעקב לא כותבים לה שורה.

שים לב

כשכתוב "בסעיף זה אין צורך להציג מעקב אחרי הפעולה foo", משתמשים בערכים שכבר חישבתם בסעיף קודם על אותו עץ, ומעקבים רק אחרי הפעולה החדשה.

דוגמה - מעקב אחר foo על עץ עם שבעה צמתים

נתונה הפעולה foo בשפת Java או Foo בשפת C#:

public static int foo(BinNode<Integer> tree)
{
    if (tree.getLeft() == null && tree.getRight() == null)
        return 0;
    if (tree.getLeft() == null)
        return foo(tree.getRight()) + 1;
    if (tree.getRight() == null)
        return foo(tree.getLeft()) - 1;
    return foo(tree.getLeft()) + foo(tree.getRight());
}

העץ: השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.
בצעו מעקב אחרי הפעולה foo והעץ, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.

פתרון
1.ארבעת המקרים בקוד: עלה - 0; רק בן ימני - foo(ימני) + 1; רק בן שמאלי - foo(שמאלי) - 1; שני בנים - סכום שני הבנים.
2.הטבלה (השורות בסדר הקריאות: 5, 1, 0, 2, 4, 7, 3 - סדר תחילי):
קריאהמצב הצומתחישובערך מוחזר
foo(5)רק בן ימני (1)foo(1) + 10
foo(1)שני בניםfoo(0) + foo(7)-1
foo(0)רק בן שמאלי (2)foo(2) - 1-2
foo(2)רק בן שמאלי (4)foo(4) - 1-1
foo(4)עלה-0
foo(7)רק בן ימני (3)foo(3) + 11
foo(3)עלה-0
3.חזרה מהרקורסיה (סדר סופי: 4, 2, 0, 3, 7, 1, 5): foo(4) = 0, ולכן foo(2) = -1 ו-foo(0) = -2. foo(3) = 0, ולכן foo(7) = 1. foo(1) = -2 + 1 = -1, ו-foo(5) = -1 + 1 = 0.
4.בדיקה: הרצה של הקוד על העץ מחזירה 0.
תשובה

הפעולה מחזירה 0.

3. פעולות רקורסיביות על עץ: ספירה, סכום, גובה ובדיקת תכונה

פעולה רקורסיבית על עץ

עץ בינרי הוא מבנה רקורסיבי: שורש, ומתחתיו שני עצים קטנים יותר. לכן הדרך הטבעית לחשב משהו על עץ היא לשאול: מה התשובה על כל אחד מתת-העצים, ואיך מצרפים ממנה תשובה לעץ כולו?
במדויק: פעולה רקורסיבית על עץ מקבלת BinNode (שורש של עץ או של תת-עץ) ובנויה משלושה חלקים: מקרה בסיס - עץ ריק (null) או עלה; שתי קריאות - על getLeft() ועל getRight(); צירוף - חיבור, מקסימום, && או || של שתי התוצאות, יחד עם הערך של הצומת. בבגרות כותבים פעולה כזו (למשל בדיקה אם עץ הוא "עץ K-שמאלי"), ומסבירים מה פעולה נתונה מחזירה.

זו אותה חשיבה כמו בפעולה רקורסיבית על שרשרת חוליות, רק עם שתי קריאות במקום אחת: בשרשרת getNext(), בעץ getLeft() ו-getRight().

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

public static int count(BinNode<Integer> t)        // מספר הצמתים
{
    if (t == null)
        return 0;
    return 1 + count(t.getLeft()) + count(t.getRight());
}

public static int sum(BinNode<Integer> t)          // סכום הערכים
{
    if (t == null)
        return 0;
    return t.getValue() + sum(t.getLeft()) + sum(t.getRight());
}

public static int countLeaves(BinNode<Integer> t)  // מספר העלים
{
    if (t == null)
        return 0;
    if (!t.hasLeft() && !t.hasRight())
        return 1;
    return countLeaves(t.getLeft()) + countLeaves(t.getRight());
}

public static int height(BinNode<Integer> t)       // גובה: עלה = 0
{
    if (t == null)
        return -1;
    return 1 + Math.max(height(t.getLeft()), height(t.getRight()));
}

public static boolean allPositive(BinNode<Integer> t)   // האם כל הערכים חיוביים
{
    if (t == null)
        return true;
    if (t.getValue() <= 0)
        return false;
    return allPositive(t.getLeft()) && allPositive(t.getRight());
}

על העץ מטבלת המינוח (השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.): count מחזירה 7, sum מחזירה 22, countLeaves מחזירה 2, height מחזירה 4, ו-allPositive מחזירה false (יש צומת שערכו 0).

מקרה הבסיס והצירוף לפי סוג השאלה

הפעולה מחזירהעץ ריק (null) מחזירצירוף
מספר צמתים / סכום01 + ... / t.getValue() + ..., ועוד שתי הקריאות
מספר עלים0עלה מחזיר 1; אחרת סכום שתי הקריאות
גובה-1 (כך עלה מקבל 0)1 + Math.max(...)
"האם כל הצמתים..."trueהצומת מקיים וגם שמאל וגם ימין (&&)
"האם קיים צומת..."falseהצומת מקיים או שמאל או ימין
דרך הפתרון

כתיבת פעולה רקורסיבית על עץ

1.מקרה בסיס: מה מחזירים לעץ ריק, או לעלה. אם השאלה אומרת שהעץ "אינו ריק", עובדים עם hasLeft() / hasRight() ולא קוראים לפעולה על null.
2.מניחים שהקריאה על תת-עץ עובדת, ושואלים רק איך מצרפים את שתי התשובות עם הצומת הנוכחי.
3.מה עובר במסלול: אם התכונה תלויה במסלול מהשורש (כמה קשתות שמאליות, באיזו רמה), מוסיפים פרמטר ומעדכנים אותו בקריאה: k - 1 כשיורדים שמאלה, k כשיורדים ימינה.
4.בדיקה: על העץ מהשאלה, על עלה בודד ועל שרוך.
דרך הפתרון

מה הפעולה מחזירה: מה כל צומת תורם

1.מפרקים את הקוד למקרים לפי סוג הצומת: עלה, רק בן שמאלי, רק בן ימני, שני בנים.
2.לכל מקרה: מה הצומת מוסיף לתוצאה של הבנים (+ 1, - 1, כלום).
3.מסכמים: כל צומת תורם פעם אחת, ולכן התוצאה היא סכום התרומות על כל הצמתים - למשל "מספר הצמתים מסוג א פחות מספר הצמתים מסוג ב".
4.בודקים את המשפט מול המעקבים מהסעיפים הקודמים.

יעילות של פעולה על עץ

n הוא מספר הצמתים בעץ.

הפעולהסיבוכיותנימוק
קריאה אחת לכל צומת, ובכל קריאה מספר קבוע של הוראותO(n)כל צומת נבדק פעם אחת, O(1) לכל צומת. כך count, height ו-isLeftK
בכל צומת קוראים לפעולה שעוברת על כל תת-העץ שלועד O(n²)במקרה הגרוע (עץ גבוה, כמו שרוך) תת-העצים בגודל n, n − 1, ...
שים לב

מקרה בסיס של עלה בלבד (כמו ב-foo) לא מטפל בעץ ריק: foo(null) נכשלת ב-tree.getLeft(). לכן השאלה מדברת על "עץ כלשהו שאינו ריק". מקרה בסיס של null (כמו ב-goo) מטפל בשניהם.

שים לב

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

דוגמה א - בדיקה אם עץ הוא עץ K-שמאלי

"עץ K-שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותר K קשתות הפונות שמאלה.
כתבו פעולה חיצונית ששמה isLeftK בשפת Java או IsLeftK בשפת C#, המקבלת עץ בינרי - root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא "עץ K-שמאלי", ואם לא - היא מחזירה false.

פתרון
1.K הוא תקציב: כמה קשתות שמאליות עוד מותר להשתמש בהן בהמשך המסלול.
2.בן שמאלי: הירידה אליו צורכת קשת שמאלית. אם התקציב 0 - העץ אינו K-שמאלי. אחרת בודקים את תת-העץ השמאלי עם k - 1.
3.בן ימני: התקציב לא משתנה; בודקים את תת-העץ הימני עם k.
4.עלה: המסלול הסתיים בלי לחרוג - true. העץ אינו ריק, ולכן בודקים hasLeft() / hasRight() לפני כל קריאה.
public static boolean isLeftK(BinNode<Integer> root, int k)
{
    if (root.hasLeft())
    {
        // ירידה שמאלה "צורכת" קשת שמאלית אחת
        if (k == 0 || !isLeftK(root.getLeft(), k - 1))
            return false;
    }
    if (root.hasRight())
    {
        // ירידה ימינה לא משנה את מספר הקשתות השמאליות
        if (!isLeftK(root.getRight(), k))
            return false;
    }
    return true;
}
5.בדיקה: על עץ הדוגמה מהשאלה (המסלול שורש → ימינה → שמאלה → שמאלה): K = 0 מחזיר false, K = 1 מחזיר false, K = 2 מחזיר true. על העץ 1-שמאלי עם 8 הצמתים (שורש 1; ל-1 בנים 2 ו-3; ל-3 בנים 4 ו-5; ל-4 בן ימני 6; ל-5 בנים 7 ו-8): K = 1 מחזיר true, K = 0 מחזיר false.
6.יעילות: כל צומת נבדק לכל היותר פעם אחת, ובכל צומת מספר קבוע של פעולות - O(n), כאשר n מספר הצמתים.
תשובה

רקורסיה עם תקציב K: בן שמאלי - אם k == 0 מחזירים false, אחרת בודקים אותו עם k - 1; בן ימני - בודקים עם אותו k; עלה - true. יעילות O(n).

דוגמה ב - מה מחזירה foo לכל עץ לא ריק

נתונה הפעולה foo בשפת Java או Foo בשפת C#:

public static int foo(BinNode<Integer> tree)
{
    if (tree.getLeft() == null && tree.getRight() == null)
        return 0;
    if (tree.getLeft() == null)
        return foo(tree.getRight()) + 1;
    if (tree.getRight() == null)
        return foo(tree.getLeft()) - 1;
    return foo(tree.getLeft()) + foo(tree.getRight());
}

כתבו בקצרה מה הפעולה foo מחזירה בעבור עץ כלשהו שאינו ריק.

פתרון
1.המקרים: עלה - 0. רק בן ימני - התוצאה של תת-העץ הימני ועוד 1. רק בן שמאלי - התוצאה של תת-העץ השמאלי פחות 1. שני בנים - רק מחברים את שתי התוצאות, בלי תוספת.
2.התרומה של כל צומת: צומת עם בן ימני בלבד תורם +1, צומת עם בן שמאלי בלבד תורם -1, עלה וצומת עם שני בנים תורמים 0. כל צומת נספר פעם אחת.
3.בדיקה מול המעקבים: בעץ 5 → 9 → 7 (ל-5 ול-9 רק בן ימני, ל-7 שני בנים 0 ו-3) יש 2 צמתים עם בן ימני בלבד ואף אחד עם שמאלי בלבד: 2 − 0 = 2, וזה מה ש-foo מחזירה. בעץ שבו foo החזירה 0 במעקב (השורש 5, ולו רק בן ימני 1. ל-1 בן שמאלי 0 ובן ימני 7. ל-0 רק בן שמאלי 2, ול-2 רק בן שמאלי 4. ל-7 רק בן ימני 3.) יש 2 עם ימני בלבד (5, 7) ו-2 עם שמאלי בלבד (0, 2): 2 − 2 = 0, כמו במעקב.
4.לא "סופרת צמתים" ולא "מחשבת גובה": התוצאה יכולה להיות שלילית, ועלים וצמתים עם שני בנים לא משפיעים עליה.
תשובה

foo מחזירה את מספר הצמתים שיש להם בן ימני בלבד, פחות מספר הצמתים שיש להם בן שמאלי בלבד.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.