יש לי עץ רב בנים -

לכל קודקוד שני מצביעים: מצביע שמאלי לבנו הבכור, מצביע ימני לאח אחריו.

אין הגבלה למספר הבנים לכל קודקוד.

אין יחס מתמטי בין קודקוד האב לבן.

בכל רמה (הבנים) מסודרים בסדר עולה.

איך מבצעים במבנה נתונים שכזה חיפוש של איבר????

הערה: בנוסף למצביע לשורש ההעץ יש לי מצביע שמטייל בעץ.

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

כדי לחפש איבר את חייבת לחפש אותו בכל רשימת בנים. (אם רשימת הבנים מיוצגת כמערך או כעץ חיפוש את יכולה להאיץ את החישוב הזה).

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

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

אני צריכה לבדוק האם איבר קיים - לא משנה לי כמה זמן זה ייקח.

אבל איך???

אני בודקת ברמה הראשונה - אני צריכה לבדוק גם בבנים של כל איבר וגם בבני בנים וכו'

צריך לשמור מצביעים? איך?כמה?איפה?

את צריכה לעבור על כל הבנים(אם הם במערך, את יכולה לבצע חיפוש בינארי) ולשמור את אלה שמתאימים לך.

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

איך אני עוברת על כל הבנים זו השאלה?????

בכל רמה יש מספר שונה של אחים לכל אחד מספר שונה של בנים וכו'

יש אפשרות לעשות כמו בחיפוש בעץ בינארי= אם לא מצאת בדוק בבנים ,אם לא מצאת בדוק באחים

איך עשים את זה?

את יכולה לבצע את זה בצורה רקורסיבית בצורה הבאה:

look-in(node n, val)
if n.val = val
return n
for each node subn in n
if look-in(subn, val) then return subn
return nil

מה זה subn ? (בן/אח?)

זה אחד הבנים של הצומת.

זה לא אמור להיות NULL ולא nil או שאני מתבלבל אם C?

זה פסאודוקוד(יעני בחפיף). יש יותר חופש.

OK