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

זה מה שכתבתי:

template <class T>
int Tree<T>::leaves(Node<T>*current)
{
	int leave;
	if(IsEmpty())
	{
		leave=0;
	}
	else
		if((root->left->value==NULL)&&(root->right->value==NULL))
	{
		leave=1;
	}
	else
	{
		????????????????????????
	}	
	return leave;
}

ב else האחרון, צריכה להיות קריאה רקורסיבית לפונקציה לתת עץ שמאל ותת עץ ימין ואיך אני סומכת בינהם??

כבר לא כתבתי כלום ב-c++ איזה 3 שנים, אז אני רק אגיד לך מה אמור להיות ואת תכתבי כבר:

int leaves(t)

if (t == null)

return 0;

if ( (t.left == null) && (t.right == null) )

return 1;

return leaves(t.left) + leaves(t.right);

במילים: אם העץ הוא null מחזירים 0.

אחרת: אם שני הבנים שלו null, כלומר הוא עלה, מחזירים 1.

אחרת: (הוא צומת פנימי ולא עלה) מחזירים את הסכום של מס' העלים בתת העץ הימני ובתת העץ השמאלי.

template <class T>
int Tree<T>::leaves(Node<T>*current)
{
	int leave;
	if(current==NULL)
	{
		return 0;
	}
	else
	{
		return leaves(current.left)+leaves(current.right)+1;
	}

}

זה עובד! אבל לא מדויק.

ניסיתי להפעיל את זה על עץ עם שורש ושני בנים, וזה מחזיר לי 3 כלומר- מספר הקודקודים בעץ!,מה לשנות????

MoRoses - הפונקציה שלך מחזירה את מספר הקודקודים בעץ, לא את מספר העלים.

הפתרון של lharpaz הוא הנכון.

יש +1 מיותר ב-return של MrRoses.

תודה.

עוד שאלה שקשורה:

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

זה מה שרשמתי בפסודו קוד:

int Tree<T>::height(Node<T>*current)
{
	if(current==NULL)
	{
		return 0;
	}
	else
	if((current->left==NULL)&&(current->right==NULL))
		{
			return 1;
		}
	else
	{
    return max(height(current->left),height(current->right));
	}
}

צריך פה +1 ב-return.

נכון, אבל:

איך אני רושמת את זה שהמחשב יקח את הגול מבין השניים (איך רושמים בשפת המחשב את max????)

פשוט וקל:

int max(int a, int b) {
 if (a>b) return a;
return b;
}

עוד שאלה....

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

אני תמיד נתקעת עם הקראיה הרקורסיבית, זה מה שכתבתי :

template <class T>
void Tree<T>::reflect(Node<T>*current)
{	
	if(current)
	{if((current->left!=NULL)&&(current->right==NULL))
		{
			current->right=current->left;
			current->left=NULL;
		}
	else
		if((current->right!=NULL)&&(current->left==NULL))
		{
			current->left=current->right;
			current->right=NULL;
		}
	else
		if((current->right!=NULL)&&(current->left!=NULL))
		{
			T temp;
			temp=current->left->value;
			current->left->value=current->right->value;
			current->right->value=temp;
		}

	reflect(current->left);
	reflect(current->right);
	}
}

הפונקציה מחליפה רק בין זוג הבנים הראשון- מה לשנוטת כדי שתמשיך (עבור כל תת עץ וכו'???)

לא נראה לי שאת צריכה לחלק ל- 3 מקרים.

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

אבל אבל אבל!!!!

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

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

1) אני אוהב מקרואים --> #define max(a, b) (a>b?a:b)

2) החלפת הבנים של העץ אמורה להתבצע כמו החלפת INTים(כשאת מחליפה בין INTים את לא בודקת אם אחד מהם שווה ל 0). עריכה: עכשיו ראיתי את הפתרון שלך. תנסי להחליף את המצביעים, ולא את הערכים.

3) הפתרון של אורך העץ אמור להיות דומה לפתרון השגוי של מספר הבנים בעץ שהוצג מקודם(אני לא זוכר מי רשם אותו), רק עם MAX במקום +. הפתרון לבעיה שרשמת לא מחזיר לך תמיד 1?

1. אני לא אוהב מקרואים. מקרואים זו גישה C-ית, לא C++-ית (ב-C++ יש inline בשביל זה).

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