צריך עזרה בפתרון שאלה במבני נתונים (פסיאודו קוד) לגבי עצים בינאריים.

[Da-Funk]

והשאלה היא: כתוב פונ' בפסיאודו קוד (יעילה ביותר מבחינת סיבוכיות זמן ריצה) שמקבלת עץ בינארי כלשהו T ומחזירה את סכום הגבהים של כל הצמתים בעץ T

הצלחתי לעשות את זה בסיבוכיות n^2 בהנחה שמס' האיברים הכללי הוא n . למשהו יש רעיון יותר יעיל ?

[Ghosthunter]

אתה יכול לעשות את זה בברקורסיה. תצייר על דף צומת מסויימת ותראה למה שווה הגובה שלה.

[Da-Funk]

עשיתי ברקורסיה אבל אני צריך את סכום הגבהים... הרקוריסה שהצעת נהרסת כשעולים יותר מרמה אחת...

[שניצל]

אז ככה:

הפונקציה שתכתוב צריכה לקבל 2 ארגומנטים - צומת, והגובה של הצומת הזה.

על מנת לקבל את סכום הגבהים בעץ אתה צריך להפעיל את הפונקציה הזו על שורש העץ ו-0 (כי גובה השורש הוא 0).

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

[Da-Funk]

אז ככה כדרישה : נניח ושם הפונ' הוא sum_heights אז הקריאה לפונ' צריכה להיות עם ארגומנט יחיד T באופן הבא .. sum_heights(T) אז מה שהצעת לא יעזור. תודה בכל אופן.

[שניצל]

אני לא חושב שתוכל עם ארגומנט יחיד.

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

[The Grey Matter]

אם הבנתי את השאלה נכונה - (סכום העומקים של כל הצמתים)

זו התשובה הפשוטה - סיבוכיות o(n)

int DepthSum(Node n,depth)
{
  if (n=null) return 0;
  leftsum=DepthSum(n.left,depth+1);rightsum=DepthSum(n.right,depth+1);
  return depth+leftsum+rightsum;
}	

[Da-Funk]

אמממ לא הבנתי איך זה עובד.. מה הערך הראשוני ש depth מקבל ? בשאלה ביקשו ממני שהפונ' תקבל ארגומנט יחיד T... עץ..

עריכה: הבנתי מה אתה מחשב ולא הבנת נכון את השאלה.. אתה מחשב עומקים אני צריך גבהים משמע עלה בעץ גובהו1 אבא שלו יהיה בגובה 2 וכו' וכו'.

[slimshady21]

אפשר עם משתנה גלובלי? כי אם כן אפשר לסרוק את כל העץ, לעלות כל פעם את המונה ב-1, ולשמור את המקסימום במשתנה הגלובלי.

ככה הפונקציה תקבל פרמטר אחד כמו שרצית, והסיבוכיות תיהיה O(n)

[Da-Funk]

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

 sum_heights(T)
     create Q
     mark_heights(T,Q)
     ...
     ...
     ... פה תישב עוד לולאה שתסכום את איברי התור (לא מקוננת)
התת פונ' שתסמן את הגבהים
     mark_heights(T,Q) 
       x=root(T)
       if (x==null) return
       a = mark_heights(Tleft(x),Q)
       b =mark_heights(Tright(x),Q)
       c= max(a,b) +1
       enqueue (Q,c)
       return c      

זה חוקי ברקורסיה ?

[Ghosthunter]

עריכה: הבנתי מה אתה מחשב ולא הבנת נכון את השאלה.. אתה מחשב עומקים אני צריך גבהים משמע עלה בעץ גובהו1 אבא שלו יהיה בגובה 2 וכו' וכו'.

אז חישבנו הפוך?

איך אתה מחשב את זה?

   0
  /\
  0 0
 /
 0

מה הגובה של השורש?

[Da-Funk]

השורש בגובה 3.. משמע המרחק ממנו לעלה הכי עמוק.. זה גובה מבחינתי

[Ghosthunter]

ומה שעשית עד עכשיו זה לרוץ(PRE ORDER) ועבור כל אחד מצאת את הגובה שלו וסכמת עם הבנים שלו?

func(t)

1. if(t!=nil)
1.1 return 0
2. else
2.1. a<-func(right(t))
2.2. b<-func(left(t))
2.3. c<-height(t)
2.4. return a+b+c

2.3 זה o(n)

ולכן כל הפונ זה o(n^2)

[Da-Funk]

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

[can_not_lose]

1) זה O של N

2) אני חושב שכדי לשבור את הראש עם התרגיל הזה בגלל שהוא חשוב ! לפני שאתה פונה לקהילה ....זה תרגיל חשוב ברקורסיה !!!

3) רמזים אפשר לתת ...BFS או חברו הטוב ..