מבנה נתונים שאלה ותשובה אפשרית

[shochat1]

מבנה נתונים שאלה ותשובה אפשרית

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

 

[ron369]

רמז: מעברים עם פלט ספציפי

כלומר, פלט שאתה מראש יכול, לפי הערכים, וללא תלות בעץ עצמו, למצוא את מצב הפלט של העץ.

 

[shochat1]

אתה יכול להבהיר לי יותר מה הכוונה

 

[shochat1]

ואגב שיטות המעבר הם

preorder וכו??

 

[ron369]

נראה לך שאני זוכר מה אומר כל דבר?

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

 

[ron369]

(איזה לא נחמד אני)

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

)

 

[ron369]

אני יכול

 

[ron369]

(אבל אני לא בטוח שהבנתי מה צריך)

(הרי כבר הסברתי, לא? פשוט למצוא שיטות סריקה, שבהן הפלט של הסריקה יהיה קבוע, ללא תלות בעץ. מה עוד צריך?

)

 

[shochat1]

מה הכוונה לללא תלות בעץ ??

 

[ron369]

ללא תלות במבנה העץ.

למשל, העצים:

5[1[2[*,*],3[*,*]],*] 5[1[2[*,*],[*,*]],[3[*,*],*]​

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

 

[ron369]

הערה:

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

 

[אמיתי ר]

כן ->

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

 

[shochat1]

חח"ע=חד חד ערכי ???

 

[ron369]

כן, כנראה.

 

[amirxbox]

תנסה הפוך

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