עץ בינארי

[galavr]

עץ בינארי ../images/Emo53.gif

מישהו יכול בבקשה להסביר לי בקצרה איך הקוד הזה עובד?

plony(x,t) if x!=null then plony(left[x]) then plony(left[x]) print x then plony(right[x])​

 

[shirbi]

יש לך שם שגיאה.

השורה השלישית והרביעית זהות. אני מניח שהן היו אמורות להופיע פעם אחת בלבד. בנוסף, השורות 4-6 צריכות להיות תחת התנאי שבשורה 2. בתכל'ס, מה זה עושה? זוהי פונקציה רקורסיבית (איזו שפה זו בכלל?) שמדפיסה את התוכן של העץ, מהאיבר השמאלי ביותר ועד האיבר הימני ביותר. בדוגמה שנתת: התחלה: 2 7 5 6 11 2 5 4 9 :סוף. האם אתה מבין למה?

 

[galavr]

אין לי שגיאה...

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

 

[galavr]

בעצם...יש שגיאונת../images/Emo163.gif

plony(x,t) if x!=null then plony(left[x]) plony(left[x]) print x plony(right[x])​

עכשיו הוא נכון

 

[yuvalmadar]

האם כל השורות בתוך הif הראשון?

אחרת תתקבל לולאה אינסופית

 

[galavr]

אכן כן.... כולן בIF

 

[עדין ר]

קוד קצת מוזר

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

2,2,7,5,5,6,11,2,2,7,5,5,6,11,2,5,4,4,9​

 

[galavr]

אתה מוכן בבקשה להסביר איך הגעת לזה?

למה מדפיס את השמאלי פעמיים...? הרי הPRINT מופיע רק אחרי הLEFT השני... ולמה בכלל הוא מדפיס את הבן הימני....?

 

[עדין ר]

שים לב שהפונקציה רקורסיבית

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

 

[galavr]

אני לא מצליח להבין את הדרך

שעושה התוכנית....

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

 

[עדין ר]

נסה להסתכל על עץ קטן יותר

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

 

[galavr]

../images/Emo7.gif

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

 

[עדין ר]

...

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

 

[galavr]

נראה לי שהבנתי...

המון תודה על הסבלנות

 

[עדין ר]

../images/Emo92.gif ../images/Emo13.gif