ערך UniVal של עץ בינארי הוא מספר הצמתים בעץ שהערך שלהם שווה לערך של האבא שלהם.

דוגמה 1:

רמה 0 (שורש) = 10

רמה 1 שמאל = 10

רמה 2 שמאל = 10

רמה 3 שמאל = 8

לעץ הזה יש שני צמתים שהערך שלהם שווה לערך של האבא שלהם, ולכן ערך ה-UniVal של העץ הוא 2.

דוגמה 2:

רמה 0 (שורש) = 10

רמה 1 שמאל = 10

רמה 1 ימין = 10

רמה 2 שמאל = 10

רמה 3 שמאל = 8

לעץ הזה יש שלושה צמתים שהערך שלהם שווה לערך של האבא שלהם, ולכן ערך ה-UniVal של העץ הוא 3.

דוגמה 3:

רמה 0 (שורש) = 10

רמה 1 שמאל = 10

רמה 2 שמאל = 10

רמה 3 שמאל = 8

רמה 4 שמאל = 8

לעץ הזה יש שלושה צמתים שהערך שלהם שווה לערך של האבא שלהם, ולכן ערך ה-UniVal של העץ הוא 3.

אני צריך פונקציה רקורסיבית בשפת C שמוצאת את ערך ה-UniVal של עץ בינארי נתון.

אשמח לקבל עזרה.

תודה מראש!

מה כבר רשמת, ואיפה הסתבכת?

int UniVal( NODE *root, int value )
{
  int RetVal = 0;

  if( root == NULL )
   return( 0 );

  if( root->info == value )
   RetVal += UniVal( root->left, root->info ) + UniVal( root->right, root->info ) + 1;
  else
   RetVal = UniVal( root->left, root->info ) + UniVal( root->right, root->info );

  return( RetVal );
}

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

נראה סבבה.

בדקת את הקוד הזה?

שתי הערות:

1. ה-if פשוט מחליט אם להוסיף 1 ל-RetVal או לא - הקריאה הרקורסיבית ל-UniVal לא תלויה בו, ולכן כדאי להשאיר אותה מחוץ ל-if.

2. מהו הערך של value בפעם הראשונה שאתה קורא ל-UniVal? שים לב שאם הוא במקרה שווה לערך של השורש, אז יתווסף לך 1 מיותר.

קודם כל הדרך הכי טובה לבדוק את הפתרונות שלך היא להריץ אותם (אתה יכול להשתמש ב Visual C++ Express Edition או ב Dev-C++ למשל).

באופן כללי הפתרון נראה נכון.

שני דברים:

- אין צורך בסוגריים מסביב לערך שאתה מחזיר.

- אין צורך ב += בהצבה ל Retval הרי הוא גם ככה 0.

אפשר לסדר את הקוד קצת אחרת:

int UniVal( NODE *root, int value )
{
  if( root == NULL )
   return 0 ;

  int RetVal = UniVal( root->left, root->info ) + UniVal( root->right, root->info );
  if( root->info == value )
   RetVal++;

  return RetVal;
}

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

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

k-o-b-y, הקוד שלך נראה יפה. תודה!

עריכה:

הקריאה הראשונית לפונקציה צריכה להיראות כך:

n = UniVal( tree, -(tree->info) );

ומה אם tree->info הוא 0?

צודק!

מה לגבי זה:

n = UniVal( tree, !(tree->info) );

יותר טוב.

(שים לב שהקריאה הזו מניחה ש-tree הוא לא NULL)

נכון!

לפני הקריאה לפונקציה צריך לבדוק האם העץ ריק.

if( tree != NULL )
  n = UniVal( tree, !(tree->info) );

אתה לא חייב לשלוח את הערך. זה יפתור לך הרבה בעיות.

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

איך אני עושה את זה?

הרקורסיה צפה מלמטה למעלה.

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

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

איך אני עושה את זה ברקורסיה?

אתה יכול בבקשה לכתוב לי את הקוד?

תתחיל לכתוב, ונתקן/נכוון אותך במידת הצורך.