עלה בעץ בינארי

הגדרה

צומת בעץ בינארי הוא עלה אם שני המצביעים שלו ל־left ול־right הם null. במילים אחרות – זה צומת ללא ילדים.

כל עץ בינארי לא ריק מכיל לפחות עלה אחד (השורש עצמו אם אין לו ילדים).

דוגמה מצוירת

בדיקה אם צומת הוא עלה

public static boolean isLeaf(BinNode<Integer> t) {
    return t != null
        && t.getLeft()  == null
        && t.getRight() == null;
}

ספירת עלים – רקורסיבית

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

זמן ריצה: O(n). שטח: O(h).

נוסחאות שימושיות

• בעץ בינארי מלא בגובה h יש בדיוק 2^h עלים ו־2^h+1 − 1 צמתים בסך הכל.
• בעץ בינארי מלא: מספר העלים = מספר הצמתים הפנימיים + 1.
• בעץ מנוון (כל צומת עם ילד יחיד): יש בדיוק עלה אחד.
• טווח אפשרי למספר העלים בעץ עם n צמתים: בין 1 ל־⌈n/2⌉.

וריאציות נפוצות בשאלות בגרות

• סכום ערכי העלים: אותה רקורסיה, רק שבמקום להחזיר 1 לעלה – מחזירים t.getValue().
• העלה הגדול ביותר: רקורסיה שמחזירה max בין הילדים, ולעלה מחזירה את הערך עצמו.
• בדיקה אם כל העלים נמצאים באותה רמה: מחשבים את רמת כל עלה ובודקים שכולם שווים.
• הדפסת המסלולים מהשורש לעלים: רקורסיה עם רשימה צוברת – מדפיסים כשמגיעים לעלה.