שאלה 3מבני נתונים2025 קיץ מועד אעצים בינארייםסה״כ 25 נק׳
עץ K־שמאלי — שרטוט וזיהוי
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים).
שימו לב
בעץ K־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). ייתכן שאין שום מסלול המכיל K קשתות הפונות שמאלה (כלומר ייתכן שבכל אחד מן המסלולים יש פחות קשתות שמאליות מ־K).
✎ דוגמה
העץ: שורש; בן שמאלי ולו בן ימני; בן ימני ולו בן שמאלי (ולו בן שמאלי ובן ימני) ובן ימני. המסלול המקווקו: שורש ← בן ימני ← בן שמאלי ← בן שמאלי
עץ זה אינועץ 1־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). כי בעץ יש מסלול שבו יותר מקשת אחת שמאלית (במסלול המקווקו יש שתי קשתות שמאליות).
לעומת זאת, עץ זה הוא עץ 2־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). כי אין בו מסלול שבו יותר משתי קשתות שמאליות (ובאותה מידה הוא גם עץ 3־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים)., וגם עץ 4־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). וכן הלאה).
משימות
אמשימה א
תרשיםניקוד לא ידוע
סרטטו עץ 1־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). (כלומר שבכל מסלול של העץ יש קשת אחת שמאלית לכל היותר), ובו 8 צמתים ומקסימום4 רמות.
במשימה ב
מימושניקוד לא ידוע
כתבו פעולה חיצונית ששמה isLeftK בשפת Java, המקבלת עץ בינרי – root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא עץ K־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים)., ואם לא – היא מחזירה false.
שפת התכנות שלי
שאלה 3מבני נתונים2025 קיץ מועד אעצים בינארייםסה״כ 25 נק׳
עץ K־שמאלי — שרטוט וזיהוי
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים).
שימו לב
בעץ K־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). ייתכן שאין שום מסלול המכיל K קשתות הפונות שמאלה (כלומר ייתכן שבכל אחד מן המסלולים יש פחות קשתות שמאליות מ־K).
✎ דוגמה
העץ: שורש; בן שמאלי ולו בן ימני; בן ימני ולו בן שמאלי (ולו בן שמאלי ובן ימני) ובן ימני. המסלול המקווקו: שורש ← בן ימני ← בן שמאלי ← בן שמאלי
עץ זה אינועץ 1־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). כי בעץ יש מסלול שבו יותר מקשת אחת שמאלית (במסלול המקווקו יש שתי קשתות שמאליות).
לעומת זאת, עץ זה הוא עץ 2־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). כי אין בו מסלול שבו יותר משתי קשתות שמאליות (ובאותה מידה הוא גם עץ 3־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים)., וגם עץ 4־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). וכן הלאה).
משימות
אמשימה א
תרשיםניקוד לא ידוע
סרטטו עץ 1־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). (כלומר שבכל מסלול של העץ יש קשת אחת שמאלית לכל היותר), ובו 8 צמתים ומקסימום4 רמות.
במשימה ב
מימושניקוד לא ידוע
כתבו פעולה חיצונית ששמה isLeftK בשפת Java, המקבלת עץ בינרי – root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא עץ K־שמאלי"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותרK קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים)., ואם לא – היא מחזירה false.
