עץ בינרי
תור ושרשרת חוליות הם "שורה": לכל איבר יש לכל היותר איבר אחד אחריו. בעץ כל צומת יכול להתפצל, ולכן הוא מתאים לייצג היררכיה: עץ משפחה, עץ קבצים, ביטוי חשבוני.
במדויק: עץ בינרי הוא עץ שבו לכל צומת יש לכל היותר שני בנים: בן שמאלי ובן ימני. בתכנית הוא בנוי משרשור של חוליות בינריות (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 |
| רמה | המרחק מהשורש בקשתות: השורש ברמה 0 | 2 ברמה 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 רמות.
| רמה | הצמתים |
|---|---|
| 0 | 1 |
| 1 | 2, 3 |
| 2 | 4, 5 |
| 3 | 6, 7, 8 |
| מסלול | קשתות שמאליות |
|---|---|
| 1 → 2 | 1 |
| 1 → 3 → 4 → 6 | 1 (3 → 4) |
| 1 → 3 → 5 → 7 | 1 (5 → 7) |
| 1 → 3 → 5 → 8 | 0 |
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());
}
}מעקב אחר פעולה רקורסיבית על עץ
foo(5) היא הקריאה על הצומת שערכו 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 והעץ, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.
foo(ימני) + 1; רק בן שמאלי - foo(שמאלי) - 1; שני בנים - סכום שני הבנים.| קריאה | מצב הצומת | חישוב | ערך מוחזר |
|---|---|---|---|
foo(5) | רק בן ימני (1) | foo(1) + 1 | 0 |
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) + 1 | 1 |
foo(3) | עלה | - | 0 |
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.הפעולה מחזירה 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) מחזיר | צירוף |
|---|---|---|
| מספר צמתים / סכום | 0 | 1 + ... / t.getValue() + ..., ועוד שתי הקריאות |
| מספר עלים | 0 | עלה מחזיר 1; אחרת סכום שתי הקריאות |
| גובה | -1 (כך עלה מקבל 0) | 1 + Math.max(...) |
| "האם כל הצמתים..." | true | הצומת מקיים וגם שמאל וגם ימין (&&) |
| "האם קיים צומת..." | false | הצומת מקיים או שמאל או ימין |
כתיבת פעולה רקורסיבית על עץ
hasLeft() / hasRight() ולא קוראים לפעולה על null.k - 1 כשיורדים שמאלה, k כשיורדים ימינה.מה הפעולה מחזירה: מה כל צומת תורם
+ 1, - 1, כלום).יעילות של פעולה על עץ
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.
k - 1.k.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;
}רקורסיה עם תקציב 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, צומת עם בן שמאלי בלבד תורם -1, עלה וצומת עם שני בנים תורמים 0. כל צומת נספר פעם אחת.foo מחזירה את מספר הצמתים שיש להם בן ימני בלבד, פחות מספר הצמתים שיש להם בן שמאלי בלבד.