שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2023 - עצי חיפוש

האם ניתן לשחזר עץ חיפוש בינרי (עח"ב) $T$ מהסריקה התוכית (in-order) שלו? לתשובה חיובית, תארו את שיטת השחזור, הסבירו מדוע היא נכונה, ונתחו את זמן הריצה שלה; לתשובה שלילית, הביאו דוגמה נגדית או הסבירו מדוע לא ניתן לשחזר (באופן חד משמעי) את העץ.

רמז: חשבו על שני עצי חיפוש בינריים שונים שנותנים את אותה סריקה תוכית.

פתרון: **תשובה: לא, לא ניתן לשחזר באופן חד-משמעי.** **דוגמה נגדית:** נתבונן בסריקה התוכית: $1, 2, 3$. עץ 1: שורש $2$, בן שמאלי $1$, בן ימני $3$. עץ 2: שורש $1$, בן ימני $2$, ול-$2$ בן ימני $3$. עץ 3: שורש $3$, בן שמאלי $2$, ול-$2$ בן שמאלי $1$. כל שלושת העצים הם עצי חיפוש בינריים חוקיים, ולכולם אותה סריקה תוכית $1, 2, 3$. לכן לא ניתן לשחזר את העץ באופן חד-משמעי מהסריקה התוכית בלבד. **הערה:** הסריקה התוכית של עח"ב תמיד נותנת את המפתחות בסדר ממוין, ללא תלות במבנה העץ. לכן אין בה מידע על המבנה.