Programma in C sugli alberi binari di ricerca

[Tipper]

Ho scritto un programma in C che genera casualmente una serie di numeri, li inserisce in un albero binario di ricerca, esegue la visita inorder, esegue la ricerca di un elemento all'interno dell'albero, trova il massimo e il minimo, e fin qui tutto ok (almeno mi pare).
Ora dovrei scrivere una funzione che calcoli l'altezza dell'albero, ovvero il numero di archi fra la radice e la foglia più lontana, solo che non so da che parte rifarmi.
Avreste qualche idea da propormi?

Grazie

[eugenio.amitrano]

Potresti inserire nella struttura del nodo oltre al valore anche un livello dove livello_figlio = livello_padre + 1 e livello_primo_nodo = 0.
Eseguire una ricerca del livello max e quella sara' l'altezza dell'albero.

Eugenio

[groucho]

mi sembra la soluzione più veloce e funzionale
io salverei il massimo addirittura durante la creazione dell'albero, figurati quanto sono pigro!

[Federico]

Potresti inserire nella struttura del nodo oltre al valore anche un livello dove livello_figlio = livello_padre + 1 e livello_primo_nodo = 0.
Eseguire una ricerca del livello max e quella sara' l'altezza dell'albero.

Eugenio

è molto semplice.
Ti fornisco lo pseudocodice,dovrebbe funzionare:

//-------------

Profondità (s) //s è la sorgente dell'albero
{
Prof=0;

for each x figlio di s do //Se non ha figli,non esegue il ciclo.
{
temp=Profondità(x)+1;
If temp>Prof then
Prof=temp;
}

return Prof;
}



Chiamante:

Prof=Profondità(Sorgente Albero);


//-----------------------------------

[Tipper]

Non ci avevo pensato ad inserire un campo con l'altezza del nodo ... grazie per l'idea, se non riesco casomai mi rifaccio vivo.

[lorven]

Potrebbe funzionare anche così:
in un qualunque algoritmo di visita, incrementare un contatore ogni volta che si scende di livello (dal link sx o dal link dx)
e decrementarlo ogni volta che si torna al nodo padre; il max valore raggiunto dal contatore corrisponderà alla profondità dell'albero.

[Tipper]

Prima di abbandonare il programma, per rilasciare la memoria precedentemente allocata, ho inserito questa riga:

Codice:

rilascia(&root);

dove &root è l'indirizzo della radice e rilascia è questa funzione:

Codice:

void rilascia(nodo *root) /* Questa funzione rilascia la memoria */
{                         /******* precedentemente allocata ******/
     nodo *root1;
     if(!(root->left==NULL)) /* Esegue questo blocco se root ha un figlio sinistro */
     {
                            root1 = root->left; /* root1 punta al figlio sinistro di root */
                            rilascia(root1); /* Viene chiamata ricorsivamente la funzione rilascia */
     }
     root1 = root; /* Preserva il valore di root */
     root->left=NULL; /* Viene eliminato il puntatore al figlio sinistro */
     root->right=NULL;/** Viene eliminato il puntatore al figlio destro **/
     free((nodo *)root); /* Rilascia la memoria */
     if(!(root1->right==NULL)) /* Esegue questo blocco se root1 ha un figlio destro */
     {
          root1 = root1->right; /* root1 punta al suo figlio destro */
          rilascia(root1); /* Chiama ricorsivamente la funzione rilascia */
     }
}


Questa funzione rilascia non mi convince per niente, ho paura che con queste chiamata ricorsive non si riesca a liberare tutta la memoria allocata.
Come posso fare?

Grazie

[bengal]

A occhio basterebbe qualcosa del tipo:

Codice:


void rilascia(nodo *x)
{
    if(x->left)
          rilascia(x->left);
    if(x->right)
          rilascia(x->right);

    free(x);
}



[Tipper]

Ho provato con questa funzione:

Codice:

void rilascia(nodo *root) /* Questa funzione rilascia la memoria */
{                         /******* precedentemente allocata ******/
     nodo *root1;
     nodo *root2;
     root1 = root;
     if(((root1->left) == NULL) && ((root1->right) == NULL)) /* Questo blocco viene eseguito se il nodo è una foglia */
     {
                       if((root1->p)!=NULL) /* Questo blocco viene eseguito se il nodo ha un padre */
                       {
                                           root2 = root1->p; /* root2 punta al padre di root1 */
                                           root2->left = NULL; /* Il puntatore al figlio sinistro di root2 viene messo a NULL */
                                           root2->right = NULL; /* Il puntatore al figlio destro di root2 viene messo a NULL */
                                           free((nodo *)root1); /* Viene rilasciato lo spazio occupato da root2 */
                                           rilascia(root2); /* Si chiama ricorsivamente rilascia() su root2, cioè sul padre di root1 */
                       }
     }
     else if(((root1->left) == NULL) && ((root1->right) != NULL)) /* Se il nodo ha un figlio destro */
     rilascia(root1->right); /* Si chiama ricorsivamente rilascia() sul figlio destro */
     else if(((root1->left) != NULL) && ((root1->right) == NULL)) /* Se il nodo ha un figlio sinistro */
     rilascia(root1->left); /* Si chiama ricorsivamente rilascia sul figlio sinistro */
     else if(((root1->left) != NULL) && ((root1->right) != NULL)) /* Se il nodo ha due figli */
     rilascia(root1->left); /* Si chiama ricorsivamente rilascia() sul figlio sinistro */
}


Ora penso che vada bene, comunque grazie bengal.