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

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

http://www.cs.bgu.ac.il/~dsis062/uploads/2762Ass2.doc

הפתרון אמור כמובן להיות בפסאודו קוד, אז תתפרעו...

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

עריכה: הבעיה נפתרה, למי שמעוניין לבדוק את הקוד שלי (פסאודו):

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

t1 זה העץ המקורי

t2 זה העץ החדש

inordersum (t1,t2,sum) return int

if t1.left!=null

new=sum+inordersum(t1.left,t2.left,sum)

newsum=sum+t1.data

t2.data=newsum

if (t1.right!=null)

return inordersum(t1.right,t2.right,newsum)

else return newsum

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

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

למישהו יש רעיון יותר טוב ?

מרפרוף בקוד שלך אני חושב שיש בעיה בפתרון שלך.. כל צומת בעץ החדש צריך להיות סכום של כל הצמתים האחרים שערכיהם קטנים מערך הצומת הזה או שווים לו. לדוגמה עבור הצומת שמכילה 15 הערך בעץ החדש יהיה 55 שהוא הסכום של 2+3+5+7+10+13+15. אני חייב כרגע ללכת אבל מאוחר יותר אני אעבור על זה ואנסה לעזור לך.

חשבתי על זה עבור 8:

sumtree(t1, t2)
---------------
1.  if p(t2) then
 1.1.  info(t2)<-info(p(t2))
2.  else
 2.1.  info(t2)<-0

3.  if left(t2) then
 3.1.  tmp<-sumtree(left(t1), left(t2))
 3.2.  info(t2)<-tmp+info(t2)+info(t1)

4.  if right(p2) then
 4.1  tmp2<-sumtree(right(t1), right(t2))

5.  return tmp+tmp2+info(t1)

מרפרוף בקוד שלך אני חושב שיש בעיה בפתרון שלך.. כל צומת בעץ החדש צריך להיות סכום של כל הצמתים האחרים שערכיהם קטנים מערך הצומת הזה או שווים לו. לדוגמה עבור הצומת שמכילה 15 הערך בעץ החדש יהיה 55 שהוא הסכום של 2+3+5+7+10+13+15. אני חייב כרגע ללכת אבל מאוחר יותר אני אעבור על זה ואנסה לעזור לך.

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

חשבתי על זה עבור 8:

sumtree(t1, t2)
---------------
1.  if p(t2) then
 1.1.  info(t2)<-info(p(t2))
2.  else
 2.1.  info(t2)<-0

3.  if left(t2) then
 3.1.  tmp<-sumtree(left(t1), left(t2))
 3.2.  info(t2)<-tmp+info(t2)+info(t1)

4.  if right(p2) then
 4.1  tmp2<-sumtree(right(t1), right(t2))

5.  return tmp+tmp2+info(t1)

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

בכל מקרה, תודה לשניכם...

יש שם את השורה הזו:

 1.1.  info(t2)<-info(p(t2))

צריך להריץ ולבדוק(לא בדקתי).