מבנה נתונים

[carlos22]

מבנה נתונים

נראה לי שיש משהו שלא הבנתי בשאלה המצורפת כי מעבר רגיל על רשימה מקושרת באורך n עם שימוש במצביע לאבר הבא יקח Ozz והוספת פעולת הדפסה תוך כדי המעבר לא תשנה את הסיבוכיות, אז למה יכולה להיות הכוונה ?

 

[גיל14]

איך אתה מייצג את העץ?

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

 

[carlos22]

אז

זה כבר פשוט עץ בינארי רגיל לא ? ואז בסעיף הרקורסיבי אפשר לעבור במעבר Pre-order, in-order, post-order רגיל, לא ? מה ההבדל בין מימוש רגיל של עץ בינארי לזה של רשימה מקושרת ?

 

[eyeball]

לדעתי

הכוונה למימוש סטנדרטי של עץ בינארי עם מצביעים לבן השמאלי והבן הימיני (להבדיל למשל מערימה הממומשת ע"י מערך).

 

[carlos22]

עדיין

נראה שאין תוכן ממש לשאלה .. הכוונה היא למעבר רגיל בכל צמתי העץ ?

 

[W12X]

ככל הנראה כן

שים לב גם לשאלה עם בדיקת הלולאות שחזרה על עצמה.

 

[גיל14]

אין הבדל - איך אתה עושה את הלא-רקורסיבי?

 

[danby]

אתה יכול בבקשה להגיד איך בנוי

n-node binary tree implemented using linked list? האם זה עץ בינארי במובן המוכר והקלאסי בו לכל NODE יש מצביעים לשני בנים?

 

[carlos22]

כן

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