preorder / postorder בעצים בינאריים

[גל אדום]

preorder / postorder בעצים בינאריים

האם אפשר לשחזר עץ בינארי בעזרת preorder או postorder? אשמח להסבר קצר כי אני לא מצליח להוכיח שאחד מהם אפשרי.

 

[ahab]

צריך עוד מידע..

אי אפשר לשחזר עץ בינארי מסריקה בודדת. את זה אין בעיה להוכיח בעזרת דוגמא פשוטה של עץ עם 3 צמתים. ברגע שיש לך 2 סריקות של העץ (לא משנה איזה, preorder, postorder, או inorder. אבל צריך 2 מתוכן), ניתן לשחזר את העץ. כדי להשתכנע ולראות איך זה נעשה, תגדיר עץ של כ-10 צמתים, תרשום תוצאות של 2 סריקות על העץ, ותנסה לשחזר מתוכן את העץ (כדאי לעבוד בצמוד להגדרת הסריקות בשלב הזה).

 

[גל אדום]

בדיוק מה שאני מנסה לעשות ולא מצליח

רשמתי סריקת preorder ו-inorder של עץ בינארי ואני מנסה לגרום איזשהו אלגוריתם שישחזר לי את העץ אבל לא ממש מצליח בזה. למשל. תוצאות הסריקות שלי יהיוף InOrder: 3,1,4,6,0,2,7,5,8 PreOrder: 0,1,3,4,6,2,5,7,8 ברור לי שאני אתחיל מpre כי הראשון בו זה השורש של העץ (0). אבל מכאן והלאה רק הסתבכתי עם אלגוריתם. נסיתי כל מיני השוואת. למשל אם הגעתי לאותו מספר בשתי הסריקות אז אני יכול מהpre להוציא את שני הבנים. אבל זה לא עובד אני חושש.

 

[DadleFish]

אתה צריך לעבוד רקורסיבית.

0 הוא שורש העץ, כלומר לפי Inorder, משמאלו תמצא 3,1,4,6 ומימינו - 2,7,5,8. עכשיו קח את 3,1,4,6. לפי ה-Preorder, השורש שלו הוא 1, ואז מתפצל לפי ה-Preorder ל-3 (משמאל) ול-4,6 מימין. וכו' וכו'.

 

[גל אדום]

צודק, רק שאני לא מצליח לרשום זאת

ברקורסיה. אני מבין היטב את ההגדרות של כל סריקה אבל מתקשה בקביעת האלגוריתם. איזה מצביעים אני מחזיק ולאן? הפונ' מקבלת את הצומת הנדרשת אבל איפשהו הלכתי לאיבוד במה שהפונ' עושה. באופן תיאורטי אין לי בעיה לעשות זאת כשאני יודע את השורש ומי מימינו ומי משמאלו, אבל לא תמיד זה ככה. יתכן ואין לו בן ימני ואני לא מצליח להבין מה התנאי עצירה שלי למעשה.

 

[DadleFish]

תנאי העצירה שלך הוא

כשהעץ שלך ריק. תשתמש במערכים, קבל שני אינדקסים לתחילת וסוף המערך, ותמשיך משם. תכתוב את האלגוריתם צעד אחרי צעד כמו שאני התחלתי אבל אפילו יותר מפורט, זהה בלוקים ופתח לאלגוריתם רקורסיבי.