altezza albero binario di ricerca

[Tony Hak]

ciao raga ! sapete come devo fare per calcolarmi con una funzione ricorsiva l'altezza di un albero ovvero il cammino massimo di quest'ultimo ? tnk's


ps con pseudocodice grazie grazie

[Vincenzo1968]

Versione ricorsiva:

int TreeDepth(Tree* head)
{
	if ( head == NULL)
	{
		 return -1;
	}
	else
	{
		int lDepth = TreeDepth(head->left);
		int rDepth = TreeDepth(head->right);

		if (lDepth > rDepth)
			return (lDepth + 1);
		else
			return (rDepth + 1);
	}
}

Versione iterativa:

int TreeDepth(Tree *head)
{
	Tree *temp1, *temp2;

	int Conta;

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
	Conta = 0;
 
	if ( head == NULL )
	{
		return -1;
	}

	temp1 = temp2 = head;

	while ( temp1 != NULL )
	{
		for(; temp1->left != NULL; temp1 = temp1->left)
		{
			stack[top++] = temp1;
			if ( Conta < top )
				Conta++;
		}

		while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
		{
			temp2 = temp1;
			if ( top == 0 )
				return Conta;
			temp1 = stack[--top];
		}

		stack[top++] = temp1;
		temp1 = temp1->right;
		if ( Conta < top )
			Conta = top;
	}

	return Conta + 1;
}

[Tony Hak]

tnk's