בקורס קודם למדתם (או הייתם אמורים ללמוד) על עצים בינאריים, ועל שלושת הדרכים לסייר בהם: preorder, inorder, postorder. במטלה הזאת המטרה היא לממש עץ בינארי עם איטרטורים שיכולים לעבור עליו בכל שלושת הסדרים.

שם המחלקה: BinaryTree. השיטות הדרושות (ראו בקובץ Demo.cpp לפרטים):

• add_root - מקבלת קלט אחד ושמה אותו בשורש של העץ. אם כבר יש משהו בשורש, הוא מוחלף.
• add_left - מקבלת שני קלטים: הקלט הראשון מציין דבר שכבר קיים בעץ. הקלט השני מציין דבר חדש שיש להוסיף בתור הילד השמאלי שלו (אם כבר יש לו ילד שמאלי - יש להחליף את התוכן שלו).
• add_right - כנ"ל, רק שהתוספת היא בתור הילד הימני.
• begin_preorder(), end_preorder() - מחזירות איטרטורים לצורך מעבר בסדר preorder (אב - שמאל - ימין).
• begin_inorder(), end_inorder() - מחזירות איטרטורים לצורך מעבר בסדר inorder (שמאל - אב - ימין).
• begin_postorder(), end_postorder() - מחזירות איטרטורים לצורך מעבר בסדר postorder (שמאל - ימין - אב).
• אופרטור פלט - מדפיס את העץ בפורמט הגיוני כלשהו לבחירתכם.

פרטים:

• העץ לא בהכרח מסודר לפי סדר עולה, ולא בהכרח מאוזן. סדר הנתונים בעץ הוא לפי האופן שבו הם מוכנסים. ראו בתוכנית הדוגמה.
• בפונקציות add_left, add_right, אם הקלט הראשון לא קיים בעץ - יש לזרוק חריגה. אם הוא קיים פעמיים או יותר - יש לבחור אחת משתי האפשרויות ולהוסיף לשם (בבדיקות האוטומטיות אל תכניסו מצבים כאלה, כדי שהתוצאה תהיה חד-משמעית).

חלק א: יש לכתוב:

• קובץ כותרת הכולל את כל הפונקציות הדרושות (ללא מימוש). שימו לב: הכותרות צריכות להיות נכונות בהתאם למה שנלמד בהרצאות - מומלץ לחזור על החומר לפני שמתחילים לכתוב.
• בדיקות מקיפות לכל הפונקציות הדרושות.
• הפקודות הבאות צריכות לעבוד ללא שגיאות:

make demo && ./demo
make test && ./test

חלק ב: בנוסף לזה:

• הפקודות make tidy, make valgrind צריכות לעבוד ללא שגיאות.
• יש לכתוב תוכנית ראשית יצירתית כלשהי המדגימה את האיטרטורים והאופרטורים שכתבתם.
• בתוכנית הראשית, להדגים את האיטרטורים בעזרת אלגוריתמים מהספריה התקנית (שנלמד בשבוע 11). האלגוריתמים לבחירתכם - תהיו יצירתיים.

אין לשנות את הקבצים הנתונים, אלא רק להוסיף קבצים חדשים.

יש לפתור את המטלה באופן עצמאי.

• מותר להתייעץ עם סטודנטים אחרים או לחפש מידע באינטרנט; אסור להעתיק קטעי-קוד שלמים מסטודנטים אחרים או מהאינטרנט.
• יש לדווח על כל עזרה שקיבלתם, מסטודנטים אחרים או מהאינטרנט, בהתאם לתקנון היושר של המחלקה.