סריקת עץ בינארי ופתרון נוסחאות נסיגה באמצעות עץ

[רוצה להיות מתכנת]

סריקת עץ בינארי ופתרון נוסחאות נסיגה באמצעות עץ

אני מתקשה בשני הדברים הנ"ל ואשמח מאוד לקבל את עזרתכם או הכוונתכם:

1) נניח שאני סורק עץ בינארי סריקת inorder, שהיא כידוע סריקה שמבצעת קודם כל מעבר על תת העץ השמאלי, אחר כך על השורש, ולבסוף על תת העץ הימני.
השאלה שלי היא האם יש חוקיות מסוימת שלפיה צריך לעבור על הקודקודים בתת העץ השמאלי (כנ"ל תת העץ הימני) ?

2) אני מתקשה בתהליך בניית עץ רקורסיה וחישוב הנוסחה הסגורה בפתרון נוסחאות נסיגה - במיוחד כאשר העץ המתקבל הוא לא מאוזן. אשמח מאוד לקבל לגבי זה סיוע מכם.

תודה רבה לכם

 

[Guy Yafe]

הרקורסיה היא החוקיות

ברגע שהגדרת שעוברים קודם על תת העץ השמאלי, ולאחר מכן על השורש ואז על הימני, את תחילי את החוקיות הזו גם על תתי העץ (זו הרקורסיה), וכך תקבלי את ה - inorder.
לדוגמה: בתת העץ המשאלי גם תתחילי מ(תת-)תת העץ השמאלי שלו וחוזר חלילה עד שתגיעי לעלה השמאלי ביותר.

4
\ /
\ /
6 2
\ / \ /
7 5 3 1

תת העץ השמאלי של השורש הוא {1,2,3}. השורש של אותו תת עץ הוא 2. ממנו גם תעברי על תת העץ השמאלי (1) ואז על השורש (2) ואז על תת העץ הימני (3).