سوال درباره درخت ها

[lighting]

سلام
برای این که تعداد برگ های یک درخت دودویی رو با ریشه T حساب کنیم من الگوریتم زیر رو براش نوشتم ایا این الگوریتم درسته؟

int getleaf (node *T){
if (T==NULL) return;
if (T->left==0 &&  T->right==0)
return getleaf(T->left)+ getleaf(T->right)
}

البته این نکته هم هست که تعداد برگ ها می شه:n0=n2+1
که n2 می شه تعداد گره درجه 2 ولی نمی دونم این مورد توی الگوریتم بازگشتی به کار می اید یا نه.​

 

[the_king]

سلام
برای این که تعداد برگ های یک درخت دودویی رو با ریشه T حساب کنیم من الگوریتم زیر رو براش نوشتم ایا این الگوریتم درسته؟

int getleaf (node *T){
if (T==NULL) return;
if (T->left==0 &&  T->right==0)
return getleaf(T->left)+ getleaf(T->right)
}

البته این نکته هم هست که تعداد برگ ها می شه:n0=n2+1
که n2 می شه تعداد گره درجه 2 ولی نمی دونم این مورد توی الگوریتم بازگشتی به کار می اید یا نه.​

شما که بجز 0 مقداری بر نگردونید.

هر گره ای بجز خود ریشه T که نه left داشته باشه و نه right یک برگ است.
اگر فرض رو بر این قرار بدهید که ریشه T خودش هیچوقت بدون فرزند نیست، نیازی به در نظر گرفتن عمق گره نیست :

int getleaf (node *T)
{
	if (T == NULL)
		return 0;
	if ((T -> left == NULL) &&  (T -> right == NULL))
		return 1;
	return getleaf(T -> left) + getleaf(T -> right);
}

اما اگر مطمئن نیستید که ریشه T فرزند داره، باید مطمئن شوید که ریشه T رو به عنوان برگ در نظر نمی گیرید،
برای شروع depth را 0 قرار می دهیم، فقط زمانی گره را برگ در نظر می گیریم که هم فرزند نداشته باشد و
هم depth بزرگتر از 0 باشد :

int getleaf (node *T, int depth)
{
	if (T == NULL)
		return 0;
	if ((T -> left == NULL) &&  (T -> right == NULL))
		if (depth > 0)
			return 1;
		else
			return 0;
	return getleaf(T -> left, depth + 1) + getleaf(T -> right, depth + 1);
}