[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
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

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>]

Originariamente inviato da 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!

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

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

Originariamente inviato da krivo

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>]

Originariamente inviato da 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

ok ci provo e vi faccio sapere

edit: funzia 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