נתונה הפעולה הבאה (הפעולה מחזירה true אם x קטן מכל הערכים בעץ t, אחרת מחזירה false; סיבוכיות זמן הריצה של הפעולה היא O(n), כאשר n מייצג את מספר הצמתים בעץ t):
נתונה הפעולה הבאה (הפעולה מחזירה true אם x קטן מכל הערכים בעץ t, אחרת מחזירה false; סיבוכיות זמן הריצה של הפעולה היא O(n), כאשר n מייצג את מספר הצמתים בעץ t):
public static boolean lessThanTree(BinNode<Integer> t, int x)
{
if (t == null)
return true;
if (!(x < t.getValue()))
return false;
return lessThanTree(t.getLeft(), x) && lessThanTree(t.getRight(), x);
}
// lessThanTree מוחזרת true אם x קטן מכל הערכים בעץ t, אחרת false. סיבוכיות זמן הריצה היא O(n), כאשר n מייצג את מספר הצמתים בעץ t.
סעיף א
כתוב פעולה חיצונית treeLessThanTree ב-Java (TreeLessThanTree ב-C#), המקבלת שני עצים בינאריים t1 ו-t2 של ערכים שלמים. הפעולה מחזירה true אם כל ערך בעץ t1 קטן מכל ערך בעץ t2, אחרת — הפעולה מחזירה false. אם t1 הוא null — הפעולה תחזיר true. אפשר להשתמש בפעולה הנתונה בלי לממש אותה בעצמך; אם אתה משתמש בפעולות אחרות, עליך לממש אותן.
public static boolean treeLessThanTree(BinNode<Integer> t1, BinNode<Integer> t2)
סעיף ב
מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיף א? נמק.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.