ABA


"צריך עזרה בעצים בינארים - יעילות"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15848 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 15848
D-KinG
חבר מתאריך 8.6.02
3490 הודעות
   00:53   27.04.10   
אל הפורום  
  צריך עזרה בעצים בינארים - יעילות  
 
   אני צריך לכתוב תוכנית שמקבלת עץ בינארי (עם תוכן של int-ים), ומדפיסה את הנתונים שבו מסודרים ע"פ רמות, מרמה 0 והלאה,
כאשר הנתונים בכל רמה יודפסו משמאל לימין...
כל זה צריך להיות ב-O(n), כאשר מס' הצמתים בעץ=n
מה שחשבתי לעשות זה לעבור על העץ פעם אחת ולמצוא את מס' הרמות - O(n)
להקצות דינמית מערך של רשימות מקושרות בגודל שמצאתי +1
לעבור על העץ עוד פעם, כאשר אני סוחב איתי משתנה שאומר לי מה הרמה שאני נמצא בה, נניח i
לגשת לתא ה-i במערך להוסיף לזנב של הרשימה המקושרת את ה-int של הצומת הנוכחי...
בסוף לעבור על כל המערך, להדפיס כל רשימה ולמחוק
השאלה אם הפעולה של ההדפסה מתבצעת ב-O(n), כי מצד אחד אני עושה פה n פעולות
(נראה לי) אבל מצד שני זה לולאה בתוך לולאה...
מה אתם אומרים? ובכלל יש פתרון פחות מסובך מזה?


                                שתף        
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

  האשכול     מחבר     תאריך כתיבה     מספר  
  מכתב ronen333  27.04.10 01:05 1
  BFS VeNom  27.04.10 11:29 2
     חח מקורי ronen333  27.04.10 11:44 3
         אחי VeNom  27.04.10 11:51 4
             אחלה ronen333  27.04.10 11:53 5
     תודה D-KinG 27.04.10 12:14 6

       
ronen333 
חבר מתאריך 20.2.03
6069 הודעות
   01:05   27.04.10   
אל הפורום  
  1. מכתב  
בתגובה להודעה מספר 0
 
   ערכתי לאחרונה בתאריך 27.04.10 בשעה 01:09 בברכה, ronen333
 
קודם כל, לולאה בתוך לולאה לא מצביע על סיבוכיות מסוימת.
דבר שני, הייתי ממליץ לך לעשות את זה עם תור (Queue).
תכניס את השורש לתור, ותעבור עם לולאה עד אשר התור ריק.
בכל פעם תכניס לתור את 2 הבנים ותשלוף.. עד שנגמר.

אם לא הבנת הנה פסדוקוד:
סרוק-לפי-רמות (T1)
אתחל-תור Q
אם לא עץ-ריק? (T1) , אזי:
הכנס-לתור (Q,T1)
כל עוד לא תור-ריק? (Q) , בצע:
הוצא-מתור (Q) ,T1
בקר בשורש של T1
אם לא עץ-ריק? (תת-עץ-שמאלי (T1)) , אזי:
הכנס-לתור (תת-עץ-שמאלי (T1),Q)
אם לא עץ-ריק? (תת-עץ-ימני (T1)) , אזי:
הכנס-לתור (תת-עץ-ימני (T1),Q)

תהנה


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
VeNom  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק
   11:29   27.04.10   
אל הפורום  
  2. BFS  
בתגובה להודעה מספר 0
 
   קח זה בטח התרגיל שאתה צריך..אתה יכול לעשות מימושים בעזרת תור ומחסנית אבל זה מה שהם מצפים ממך..אם אתה צריך עוד תרגילים שלח לי הודעה בפרטי..

void printByLevelsHelper(TreeNode *root)//using the bsf algroithm to go through the tree
{
TreeNode* arr[SIZE]={0};//help array of treenodes(size is 20 for this spec. tree(you can change the size on the define for larger trees).
int size=0,index=0;
while(root)
{
printf("%d ",root->data);
if(root->left)
arr[size++] = root->left;
if(root->right)
arr[size++] = root->right;
root = arr[index++];
}
}
void printByLevels(Tree tr)
{
if(!tr.root)//empty tree check
return;
else
printByLevelsHelper(tr.root);
}
[\code]



                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ronen333 
חבר מתאריך 20.2.03
6069 הודעות
   11:44   27.04.10   
אל הפורום  
  3. חח מקורי  
בתגובה להודעה מספר 2
 
   ערכתי לאחרונה בתאריך 27.04.10 בשעה 11:51 בברכה, ronen333
 
קצת מגביל בגלל שאתה צריך לדעת את הגודל אבל מקורי..
וסתם הערה, לא יודע אם לא שמת לב אבל עשית ב printByLevels בדיקה מיותרת...
יכלת פשוט לעשות כך:

void printByLevels(Tree tr)
{
if(tr.root)
printByLevelsHelper(tr.root);
}


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
VeNom  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק
   11:51   27.04.10   
אל הפורום  
  4. אחי  
בתגובה להודעה מספר 3
 
   כתבתי את התרגיל שהייתי בשנה א'...היום אחרי קורסים כמו מבני נתונים ואלגוריתמים הייתי כותב אותו אחרת לגמרי..
ואם בא לך תשלח לפונקציית עזר את גודל העץ(או לחילופין תריץ פונקציה שעושה inorder בלינאריות ותשלח לפונקציה את גודל העץ..תקצה מערך דינמי בגודל העץ ותשחרר אותו..זה סתם לשם הדוגמא..והייתי בשנה א' שוב באמת שלא ידעתי יותר מדי..


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ronen333 
חבר מתאריך 20.2.03
6069 הודעות
   11:53   27.04.10   
אל הפורום  
  5. אחלה  
בתגובה להודעה מספר 4
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
D-KinG
חבר מתאריך 8.6.02
3490 הודעות
   12:14   27.04.10   
אל הפורום  
  6. תודה  
בתגובה להודעה מספר 2
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net