1) אם ברשותך מערך
ממוין של נתונים, כיצד תכניס אותם לעץ חיפוש בינארי כך שהוא יהיה
מאוזן ככל האפשר?
תשובה
תשובה: נשתמש בפונקציה רקורסיבית. פונקציה זו תיקח
את האיבר האמצעי במערך בתור השורש של העץ. אז היא תקרא לעצמה פעמיים
כדי לבנות עצים מהחצי השמאלי והחצי הימני של המערך, ותשים אותם בתור
הבן השמאלי והימני של השורש בהתאמה. תנאי הקצה יהיה מערך ריק, שעבורו
הפונקציה תחזיר עץ ריק.
הסתר תשובה
2) אם לכל איבר יש מצביע להורה שלו, כיצד ניתן
לעבור מאיבר מסוים לאיבר הבא בעץ לפי סדר המיון?
תשובה
תשובה: אם לאיבר יש בן ימני, האיבר הבא בעץ הוא האיבר
המינימלי בתת העץ הימני. אחרת: נעלה להורה של האיבר. אם האיבר היה
בן שמאלי, אז ההורה הוא האיבר הבא. אם הוא היה בן ימני, נמשיך בצורה
זו. אם הגענו לשורש (מכיוון הבן הימני) אז האיבר היה המקסימלי בעץ.
הסתר תשובה
3) כיצד ניתן לחשב גובה עץ חיפוש בינארי? (גובה
העץ הוא אורך המסלול הארוך ביותר מהשורש לעלה).
תשובה
תשובה: נחשב בצורה רקורסיבית את גובה תת העץ הימני
והשמאלי, ניקח את המקסימלי מבין שניהם ונוסיף 1.
הסתר תשובה
