[C] deallocazione di un albero binario

[<Gabrik>]

Salve ragazzi, ho un piccolo problema, non riesco a capire come deallocare tutti i nodi di un albero :muro:
mi spiego meglio ho un albero binario, e alla chiusura del programma lo devo deallocare, quindi io ho pensato di fare una funzione ricorsiva che a partire da ogni nodo dealloca prima quelli alla sinistra, poi quelli alla destra e infine il nodo, ma pare non funzionare perché in esecuzione mi ritorna

albero(302) malloc: *** error for object 0x1001000a8: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Dealloco...Abort trap


:mbe:

l'albero è strutturato con in questo modo

typedef struct nodoABR
{
tipobaseABR info; /* tipo di informazioni contenute nel nodo*/
struct nodoABR *leftchild,*rightchild;
} *abr;

e la funzione che dealloca

void DeallocaABR(abr *p)
{
if(EmptyABR(*p)) /* se il nodo non ha figli lo dealloco direttamente */
free(p);
else /* altrimenti vado a sinistra poi a destra e infine lo dealloco */
{
DeallocaABR(&(*p)->leftchild);
DeallocaABR(&(*p)->rightchild);
free(p);
}
}

idee?? è una giornata che all'uni mi sbatto su sto codice ma non riesco a cavarne niente

[krivo]

penso che il problema risieda nel fatto che tu disallocando un nodo qualsiasi(e i suoi figli) quando vai a disallocare il padre, riprovi a disallocare anche il figlio e questo ti dà errore
infatti dice errore: il puntatore che si sta deallocando (freed) non è allocato, perchè lo potresti aver deallocato poco prima!
una soluzione potrebbe essere per ogni nodo deallocare i figli ma non il nodo stesso, tranne che per la radice, magari introducendo un puntatore al nodo padre o una variabile su cui controlli che il nodo sia radice o meno

[clockover]

prova una soluzione del genere

dealloca_albero(nodo n){
if n == NULL return;
nodo *l = n->left
nodo *r = n->right
free(n)
if(l != NULL) dealloca_albero(l)
if(r != NULL) dealloca_albero(r)
}

il controllo all'inizio potrebbe anche non servire se sei sicuro che la radice non è NULL, ma meglio mettercelo

edit:
volendo infatti potresti omettere i controlli tipo if l != NULL e r != NULL dato che appena richiamata ricorsivamente la funzione effettua il controllo, ma in termini di prestazioni è molto meno costoso un controllo che una chiamata ricorsiva

[<Gabrik>]

penso che il problema risieda nel fatto che tu disallocando un nodo qualsiasi(e i suoi figli) quando vai a disallocare il padre, riprovi a disallocare anche il figlio e questo ti dà errore
infatti dice errore: il puntatore che si sta deallocando (freed) non è allocato, perchè lo potresti aver deallocato poco prima!

ci avevo pensato anche io ma poi mi sono detto se prima vado nei figli e solo dopo faccio la free() perché fà così :muro:

il bello è che dà problemi anche se l'albero è formato dalla sola radice


una soluzione potrebbe essere per ogni nodo deallocare i figli ma non il nodo stesso, tranne che per la radice, magari introducendo un puntatore al nodo padre o una variabile su cui controlli che il nodo sia radice o meno

se faccio un puntatore al padre il proff mi uccide appena legge il codice,
comunque lui prende *p sempre come se fosse una radice, controlla se ha figli e poi fà quello che deve fare, piuttosto credo di aver fatto casino sui puntatori quando faccio &(*p)->leftchild e &(*p)->rightchild

[<Gabrik>]

prova una soluzione del genere

dealloca_albero(nodo n){
if n == NULL return;
nodo *l = n->left
nodo *r = n->right
free(n)
if(l != NULL) dealloca_albero(l)
if(r != NULL) dealloca_albero(r)
}

il controllo all'inizio potrebbe anche non servire se sei sicuro che la radice non è NULL, ma meglio mettercelo

edit:
volendo infatti potresti omettere i controlli tipo if l != NULL e r != NULL dato che appena richiamata ricorsivamente la funzione effettua il controllo, ma in termini di prestazioni è molto meno costoso un controllo che una chiamata ricorsiva
ok ci provo e vi faccio sapere ;)

edit: funzia :D grazie adesso devo capire cosa ha che non và la mia soluzione, anche se credo e sono convinto di aver fatto casino con i puntatori a left e right

edit2: confermo avevo fatto casino con i puntatori infatti modificando la funzione così


void DeallocaABR(abr a)
{
if(EmptyABR(a))
free(a);
else
{
DeallocaABR(a->leftchild);
DeallocaABR(a->rightchild);
free(a);
}
}

funziona grazie a tutti :D