UniVal Tree

[3d7]

ערך 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 של עץ בינארי נתון.

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

תודה מראש!

[Ghosthunter]

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

[3d7]

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 מיותר.

[k-o-b-y]

קודם כל הדרך הכי טובה לבדוק את הפתרונות שלך היא להריץ אותם (אתה יכול להשתמש ב 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;
}

[3d7]

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

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

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

עריכה:

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

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

[שניצל]

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

[3d7]

צודק!

מה לגבי זה:

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

[שניצל]

יותר טוב.

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

[3d7]

נכון!

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

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

[Ghosthunter]

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

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

[3d7]

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

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

[שניצל]

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

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

[3d7]

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

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

[Ghosthunter]

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