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

[saar85]

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

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

אודה לעזרתכם!

 

[הפרבולה]

נראה לי שאפשר ברקורסיה

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

אתה מוזמן לחשוב על הפרטים....

 

[saar85]

השאלה איך להפוך את זה לרשימה מקושרת

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

 

[BravoMan]

אז בוא נתחיל מכמה שאלות מנחות:

אתה יודע איך עוברים על עץ ב-pre-order?
&nbsp
האם אתה יודע לסדר עץ בגובה 1 (ללא ענפים) כרשימה מקושרת?
מה לגבי עץ בגובה 2 (שורש ועלים)?

 

[saar85]

כן

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

 

[selalerer]

קודם כל תכתוב פונקציה שיודעת להפוך עץ עם node אחד...

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