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 ;)