bigger סופרת צמתים בעץ בינארי שערכם גדול ממספר נתון. bigInTree משלבת אותה עם מחסנית: לכל ערך שנשלף מ-s, בונה Item עם הערך ועם ספירת הצמתים הגדולים ממנו בעץ bt.
bigger סופרת צמתים בעץ בינארי שערכם גדול ממספר נתון. bigInTree משלבת אותה עם מחסנית: לכל ערך שנשלף מ-s, בונה Item עם הערך ועם ספירת הצמתים הגדולים ממנו בעץ bt.
class Item
{
private int num;
private int bigNum;
public Item(int n, int b)
{
this.num = n;
this.bigNum = b;
}
// get/set — לא מוגדרים במפורש בשאלון; אין נגישות מפורשת נדרשת, נוספו לפי הצורך
}
עץ בינארי bt ומחסנית s לדוגמה (עמוד 11 java / עמוד 26 csharp, אומת מתמונת ה-PDF).
עץ bt: 7
/ \
4 1
/ \
9 5
מחסנית s (מהראש לתחתית, סדר pop): 2, 10, 6
לאחר bigInTree(bt,s) — מחסנית תוצאה (מהראש לתחתית): Item(6,2), Item(10,0), Item(2,4)
(עבור 2: 4 צמתים גדולים מ-2 בעץ [7,4,9,5]; עבור 10: 0 צמתים; עבור 6: 2 צמתים גדולים מ-6 [7,9])
כתבו פעולה bigger המקבלת עץ בינארי t של מספרים שלמים ומספר שלם x ומחזירה את מספר הצמתים בעץ t שערכם גדולים מ-x.
public static int bigger(BinNode<Integer> t, int x)
נתונה המחלקה Item הבאה (ראו code_context). כתבו פעולה bigInTree המקבלת עץ בינארי bt ומחסנית של מספרים שלמים s ומחזירה מחסנית שבה כל איבר הוא מטיפוס Item שמכיל ערך ממחסנית s ומספר האיברים הגדולים ממנו שנמצאים בעץ bt.
public static Stack<Item> bigInTree(BinNode<Integer> bt, Stack<Integer> s)
מהי הסיבוכיות של זמן הריצה של הפעולה? הסבירו את תשובתכם. ההסבר חייב להתייחס גם למספר צמתים בתור וגם למספר איברים במחסנית.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.