יש לי תכנית הסורקת עץ ומדפיס את הערכים לפי הרמות.

אבל-

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

זו התכנית:

אם לא עץ ריק (T) אז :

אתחל תור (Q)

הכנס לתור (T,Q)

כל עוד התור לא ריק? (Q) בצע

הוצא מהתור .

התייחס ל-T:

אם לא עץ ריק? (תת עץ שמאלי(T) -הכנס לתור תת עץ שמאלי(T,Q)

אם לא עץ ריק? (תת עץ ימני(T) -הכנס לתור תת עץ ימני(T,Q)

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

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

נראה לי שאפשר להוכיח את זה ככה -

1. בן מטופל תמיד אחרי האבא שלו. (נראה לי די ברור למה)

2. בן שמאלי מטופל מיד לפני בן ימני (בגלל הסדר שהם מוכנסים לעץ)

נניח שעד רמה n האלגוריתם עבר לפי הרמות ובתוך רמה, עבר לפי הסדר משמאל לימין. (בגלל 1 ו- 2 בסיס האינדוקציה מתקיים עבור n=2)

נניח בשלילה שברמה n+1 יש צומת X שטופלה לפני הצומת שמשמאלה Y.

לפי 2, ל- X ו- Y אין אבא משותף, אבל אם נסתכל על האבות של X ו- Y ברמה n (נקרא להם X' ו- Y'), אז מהנחת האינדוקציה X' טופל אחרי Y', ולכן X הוכנס לתור אחרי Y. לכן בתוך אותה רמה הצמתים יטופלו לפי הסדר.

נניח עכשיו בשלילה שברמה n+1 יש צומת X שטופלה לפני צומת Z ברמה n.

נקרא לאבא של X, X'.

לפי 1: Z הוא לא X'.

אם Z מופיע לפני X'(ברמה n), אז ברור שהוא (Z) מטופל לפניו, ולכן גם לפני X.

אם לא, זה אומר שה- X' יצא מהתור לפני ש- Z נכנס אליו, אבל זה גם אומר שהאבא של X' יצא מהתור לפני שהאבא של Z נכנס אליו, וכך עד לאב הקדמון המשותף הראשון (W) של X' ו- Z, שבו הבן השמאלי X* הוא אב קדמון של X' והבן הימני Z* הוא אב קדמון של Z. כיון ש- Z* נכנס לתור כאשר W טופל, זה קרה לפני ש- X* טופל (לפי 1) ולכן, לא יכול להיות ש- X טופל לפני Z.

כלומר, הוכחנו את שלב האינדוקציה, וסיימנו.

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

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

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

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

אופס...

הערה: תגובה זו נכתבה בלשון זכר אך מיועדת לשני המינים

אם אינני טועה קוראים לשיטה הזו BFS. תרשמי ליד כל צומת מתי נכנסת ומתי יצאת ממנוף כאשר דילוג בין צמתים(או עלים) מעלה את הזמן שלך ב- 1.

עריכה: הנה: http://en.wikipedia.org/wiki/Breadth-first_search .

BFS הוא אלגוריתם כללי יותר לטיפול בגרפים, לא רק בעצים, אבל הוא עובד כמובן אם מריצים אותו מהשורש.