[C] Eliminazione elemento da un albero binario

[Lasentinella]

Ciao a tutti!
Nel programma sugli alberi che sto facendo, devo eliminare tutti i nodi.

void elimina(TREE *p_T) {

   if(*p_T!=NULL)
   {
     if ((*p_T)->left!=NULL)
        elimina(&(*p_T)->left); 
   
     if ((*p_T)->right !=NULL) 
        elimina(&(*p_T)->right);
         
     *p_T=NULL;
     free(*p_T);
   }
   else
     *p_T=NULL;
}

Vorrei chiedervi se è giusto..a me non sembra, perché probabilmente il programma pone a NULL i vari nodi ma non li libera. Ma allora come fare? Sapreste dirmelo?

Grazie

[Mods]

Mi verrebbe da dire che devi scambiare le ultime 2 righe dell'if senza asterisco

free(p_T);
p_T=NULL;

Prima liberi la memoria e poi poni il puntatore a NULL...

[Lasentinella]

Originariamente inviato da Mods
Mi verrebbe da dire che devi scambiare le ultime 2 righe dell'if senza asterisco

free(p_T);
p_T=NULL;

Prima liberi la memoria e poi poni il puntatore a NULL...

sì ho messo *p_T=NULL; (con l'astrerisco) perché p_T è di tipo TREE (e TREE è di tipo puntatore a nodo)...però mi vengono i dubbi sugli aterischi ora :master:
volevo chiederti: se inverto in questo modo, non si può togliere p_T=NULL?
La free non dovrebbe eliminare p_T? Quindi non si può evitare di porre poi p_T a NULL?

[Mods]

sì, giusta osservazione!
E' ke molto spesso si usa farlo una volta liberato lo spazio di reimpostare il puntatore a NULL in modo da evitare errori di semantica...
metti per esempio che per sbaglio successivamente tenti di leggere/scrivere un dato cancellato sfruttando quel puntatore. Questo ti punterebbe ad una zona non allocata, generando errori che il C non ti avvisa...
Inoltre impostando a NULL è più facile verificare che la lista, albero, o cos'altro sia esista/non esista...
il controllo diverebbe banalmente un

if(p==NULL) <è vuota>

[Lasentinella]

Originariamente inviato da Mods
sì, giusta osservazione!
E' ke molto spesso si usa farlo una volta liberato lo spazio di reimpostare il puntatore a NULL in modo da evitare errori di semantica...
metti per esempio che per sbaglio successivamente tenti di leggere/scrivere un dato cancellato sfruttando quel puntatore. Questo ti punterebbe ad una zona non allocata, generando errori che il C non ti avvisa...
Inoltre impostando a NULL è più facile verificare che la lista, albero, o cos'altro sia esista/non esista...
il controllo diverebbe banalmente un

if(p==NULL) <è vuota>

capito!Grazie
Però non riesco a farlo funzionare..cioé io scrivo questo:

if(*p_T!=NULL)
   {
     if ((*p_T)->left!=NULL)
        elimina(&(*p_T)->left);
        
     if ((*p_T)->right !=NULL) 
        elimina(&(*p_T)->right);
     
     free(*p_T);

   }
   else
     *p_T=NULL;
}

tenendo conto che TREE è dichiarato in questo modo:

typedef struct nodo *TREE;
struct nodo {
  SCHEDA sc; 
  TREE left; 
  TREE right;
};

ma la cancellazione non ha successo...rimane tutto lì dov'è

Ho provato anche con free(p_T); ma non succede nulla lo stesso..

[Mods]

metti ancora degli asterischi di troppo
Non devi porre a NULL i valori, ma i loro puntatori...
un funzione ricorsiva semplice che rispetta un po' tutti gli std può essere questa

void elimina(TREE p_T){
     if(p_T==NULL)
                  return;
     
     elimina(p_T->left);
     elimina(p_T->right);
     
     free(p_T);
     p_T=NULL;  
}

[Lasentinella]

Originariamente inviato da Mods
metti ancora degli asterischi di troppo
Non devi porre a NULL i valori, ma i loro puntatori...
un funzione ricorsiva semplice che rispetta un po' tutti gli std può essere questa

void elimina(TREE p_T){
     if(p_T==NULL)
                  return;
     
     elimina(p_T->left);
     elimina(p_T->right);
     
     free(p_T);
     p_T=NULL;  
}

Scusa ma mi ero dimenticato di specificare che devo tenere la dichiarazione della funzione così com'è (mi è stata data dal professore), ovvero questa:
void elimina(TREE *p_T) ;
e quindi il problema dei puntatori rimane
Se metto elimina(p_T->left); e elimina(p_T->right); ottengo l'errore "request for member in something not a structure or union"

[Mods]

Ah sì, scusami, nella fretta di scrivere direttamente sul forum e non testare (mea culpa) ho sbagliato alcune cose... il passaggio ke facevo io veniva per valore e quindi liberava ma nn assegnava NULL ad un bel niente...
la soluzione dovrebbe essere questa...

void elimina(TREE* p_T){
     if(*p_T==NULL)
                  return;
     
     elimina(&(*p_T)->left);
     elimina(&(*p_T)->right);
     
     free(*p_T);
     *p_T=NULL;  
}

In pratica è più o meno il tuo, eliminando i due IF... scusami l'errore... la prox volta farò più attenzione...
Il mio invece andava bene nel caso ci mettevo la & nel parametro, in modo da passarlo per indirizzo, però quello è C++...

Prova a vedere ... dovrebbe funzionare stavolta....

[Lasentinella]

Originariamente inviato da Mods
Ah sì, scusami, nella fretta di scrivere direttamente sul forum e non testare (mea culpa) ho sbagliato alcune cose... il passaggio ke facevo io veniva per valore e quindi liberava ma nn assegnava NULL ad un bel niente...
la soluzione dovrebbe essere questa...

void elimina(TREE* p_T){
     if(*p_T==NULL)
                  return;
     
     elimina(&(*p_T)->left);
     elimina(&(*p_T)->right);
     
     free(*p_T);
     *p_T=NULL;  
}

(spostando opportunamente i figli)

In pratica è più o meno il tuo, eliminando i due IF... scusami l'errore... la prox volta farò più attenzione...
Il mio invece andava bene nel caso ci mettevo la & nel parametro, in modo da passarlo per indirizzo, però quello è C++...

Prova a vedere ... dovrebbe funzionare stavolta....

Sì funziona, grazie mille!
Ora vorrei chiedere una cosa un pò più complicata (va bene anche sapere i passaggi da fare e poi ci provo).. cancellazione di un singolo nodo:
-se left è NULL e right no pongo il nodo uguale al nodo->right (spostando opportunamente i figli)
-se right è NULL e left no pongo il nodo uguale al nodo->left(spostando opportunamente i figli)

- se sia right che left NON sono nulli, come faccio?
Girando in Internet ho trovato una serie di soluzioni una più incomprensibile dell'altra VVoVe:

[ilmo lesto]

la cancellazione di un singolo nodo dall'albero binario comporta un algoritmo piuttosto complesso che può essere suddiviso idealmente in tre casi

caso 1: il nodo che vuoi eliminare non ha figli
caso 2: il nodo ha un solo figlio
caso 3: il nodo ha due figli.

nel primo caso bisogna procedere semplicemente eliminando il nodo e impostandolo a NULL.
nel secondo caso si elimina il nodo, e il nodo figlio prende il posto di quello del padre.
nel terzo caso (quello più complesso) bisogna sostituire il nodo che si vuole eliminare con il valore più piccolo del sottoalbero che sia maggiore del nodo che vorresti eliminare.
vale a dire che devi percorrere tutto l'albero (partendo dal nodo che vuoi eliminare) andando sempre a sinistra ossia dovrai scriverti una funzioncina che trovi il valore minimo in un albero di ricerca binaria, una cosa del genere

TREE* minimo (TREE *p_T){
	
	if (*p_T->left != NULL)
		return minimo (*p_T->left);	
	
	else
		return *p_T;
}

tempo fa avevo scritto l'algoritmo, ma, come tu hai detto, è piuttosto lungo e complesso... non so se esista un metodo più veloce...