עצים בינאריים - מדעי המחשב ב'

[ZeppeliN]

היי..

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

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

"עץ מכפלה" הוא עלה או עץ בינרי , שערך השורש הוא מכפלת ערכי

צאצאיו, וכל אחד מתתי העצים שלו הוא "עץ מכפלה".

א. לפניך עצים בינאריים הבאים :

(צד שמאל זה A וצד ימין זה D)

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

ב. כתוב פעולה המקבלת כפרמטר עץ בינרי ומחזירה "אמת" אם הוא "עץ

מכפלה" ,אחרת יוחזר "שקר".

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

תודה רבה!

----------------

Now playing: Yoni Bloh - סיבה לעזוב

via FoxyTunes

[sir f]

נראה לי שהבעיה היא האם מדובר פה במכפלת כל הצאצאים כולל צאצאי צאצאים או רק צאצאים ישירים מדרגה ראשונה, לא?

[yossi314]

אתה בסה"כ בודק אם בן X בן = אבא, זה כל הקוד.

כל העצים עונים על זה, מלבד העץ הימני ביותר.

[ZeppeliN]

אתה בסה"כ בודק עם בן X בן = אבא, זה כל הקוד.

כל העצים עונים על זה, מלבד העץ הימני ביותר.

אבל צאצא זה גם "נכדים" ו"נינים" ועוד, לא?

[sir f]

תחפש בספרים שלך מה ההגדרה המדויקת.

[binyamin1001]

ע"פ הניסוח של השאלה, עץ בינארי הוא עץ מכפלה אם מתקימים התנאים הבאים:

בן שמאל X בן ימין = ערך השורש.

בן שמאל הוא עץ מכפלה.

בן ימין הוא עץ מכפלה.

ולכן הקוד הפשוט הוא:

bool product(tree* T)
{
   if(T == NULL) return true;
   if( T->right * T->left == t->Value) return ( true && product(T->right) && product(T->left)
   return false;
}

נ.ב.

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

לילה טוב, ובהצלחה במבחן שלך מחר!

[שניצל]

קודם כל, לעשות true && זה חסר משמעות.

חוץ מזה, T->right ו-T->left הם לא מספרים, אלא nodes בעץ. אי אפשר לכפול ביניהם, צריך לכפול את T->left->value ו-T->right->value (ולבדוק קודם כל שאין null, כמובן).

[binyamin1001]

קודם כל, לעשות true && זה חסר משמעות.

אני מודע לזה, ציינתי בעצמי שזה עלול להיות מיותר.

חוץ מזה, T->right ו-T->left הם לא מספרים, אלא nodes בעץ. אי אפשר לכפול ביניהם, צריך לכפול את T->left->value ו-T->right->value (ולבדוק קודם כל שאין null, כמובן).

צודק, טעיתי.

אני מניח שהקוד המתוקן הוא משהו בסביבות:

bool product(tree* T)
{
   if(T == NULL) return true;
   if(T->right == NULL && T->left == NULL) return true;
   if(T->right == NULL) return ( (T->left == T->value) && product(T->left) );
   if(T->left == NULL) return ( (T->right == T->value) && product(T->right) );

   if( T->right->Value * T->left->Value == t->Value) return (product(T->right) && product(T->left) );
   return false;
}

תקנו אותי אם אני טועה.

[שניצל]

אתה טועה

אתה צריך לעשות T->left->value == T->value, ולא T->left == T->value (ואותו דבר לגבי right).

[binyamin1001]

אתה טועה

אתה צריך לעשות T->left->value == T->value, ולא T->left == T->value (ואותו דבר לגבי right).

צודק.

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

תודה על ההערות!

נ.ב.

מישהו יודע איך הלך לפותח הנושא במתכונת?

[Ghosthunter]

אהא, אולי תנסה למחזר בצורה נכונה כך שזה יעבוד ב- 2 המקרים (כמובן בתנאי שזו אותה תוכנית).

[binyamin1001]

אהא, אולי תנסה למחזר בצורה נכונה כך שזה יעבוד ב- 2 המקרים (כמובן בתנאי שזו אותה תוכנית).

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

[Ghosthunter]

אולי תכתוב ספריה(קובץ H) משלך עם כל הדברים שאתה מרבה להשתמש בהם.