Buonasera a tutti.
Come da titolo sto lavorando sull'implementazione di alcune funzioni per la gestione degli alberi, funzionano tutte tranne quella per la cancellazione dei singoli nodi, nello specifico quando devo cancellare una foglia(un nodo che non ha figli).
In teoria quando il codice riconosce che ad essere eliminata è una foglia prima libera la memoria allocata al puntatore e poi lo inizializza a NULL.
In pratica il programma da errore di segmentazione e viene terminato.
Nonostante siano ore che ci lavoro non riesco a venirne a capo, qualcuno può aiutarmi?
codice:
#include<stdio.h>#include<stdlib.h>
#include<stdbool.h>
struct node
{
int value;
struct node *sx;//puntatore al nodo a sinistra
struct node *dx;//puntatore al nodo a destra
};
typedef struct node *tree;
int restituisci_valore(tree N)
{
if(N==NULL)
return 0;
else
return N->value;
}
tree nuovo_albero(void)
{
return NULL;
}
bool albero_vuoto(tree T)
{
return T == NULL;
}
tree inserisci_elemento(tree T, int val)//qui vengono inseriti gli elementi voluti dall'utente
{
if(T==NULL)
{
T=(tree)malloc(sizeof(tree));
T->value = val;
T->sx = NULL;
T->dx = NULL;
}
else
{
if((T->value) < (val))
{
T->dx = inserisci_elemento(T->dx, val);
}
if((T->value) > (val))
{
T->sx = inserisci_elemento(T->sx, val);
}
}
return T;
}
tree restituisci_radice(tree T)
{
return T;
}
void stampa_tutto(tree W)
{
if(W==NULL)
{
return;
}
else
{
stampa_tutto(W->sx);
printf("%d\n", W->value);
stampa_tutto(W->dx);
}
}
void cancellazione_elemento(tree Y, int elem)
{
if(Y->value < elem)
cancellazione_elemento(Y->dx, elem);
if(Y->value > elem)
cancellazione_elemento(Y->sx, elem);
else//se Y->value risulta uguale all elemento che vogliamo eliminare
{
if(Y->sx == NULL && Y->dx == NULL)
{
free(Y);
Y=NULL;
}
if(Y->sx != NULL && Y->dx == NULL)
{
Y->value = Y->sx->value;
free(Y->sx);
Y->sx=NULL;
}
if(Y->sx == NULL && Y->dx != NULL)
{
Y->value = Y->dx->value;
free(Y->dx);
Y->dx=NULL;
}
if(Y->sx != NULL && Y->dx != NULL)
printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
}
stampa_tutto(Y);
}
void distruggi_albero(tree T)
{
if(T->sx != NULL)
{
distruggi_albero(T->sx);
}
if(T->dx != NULL)
{
distruggi_albero(T->dx);
}
if((T->sx == NULL) && (T->dx == NULL))
{
free(T);
}
if(albero_vuoto(T))
return;
}
void ricerca_ricorsiva(tree W, int num)
{
if(albero_vuoto(W)==true)
printf("L'albero non contiene il tuo elemento\n");
if(W->value > num)
ricerca_ricorsiva(W->sx, num);
if(W->value < num)
ricerca_ricorsiva(W->dx, num);
if(W->value == num)
printf("Il numero da te cercato esiste nel tuo albero!\n");
}
void scansione(tree T)
{
tree W=T;
int num;
printf("Che numero vuoi cercare? ");
scanf("%d", &num);
if(albero_vuoto(T)==true)
printf("Non posso eseguire una ricerca su un albero vuoto, chiudo bottega\n");
else
ricerca_ricorsiva(W, num);
}
int main(void)
{
tree T=nuovo_albero();
int val,tot,elem;
printf("Con questo programma creeremo un albero binario ordinato\nQuanti elementi vuoi inserire? ");
scanf("%d", &tot);
for(int i=0; i<tot; i++)
{
printf("Qual'è il %d° elemento che vuoi inserire? ", (i+1));
scanf("%d", &val);
T=inserisci_elemento(T, val);
}
printf("Ora stampiamo il tuo albero binario ordinato!\n");
tree W=T;
stampa_tutto(W);
//scansione(T);
tree Y=T;
printf("Cancelliamo un elemento dall albero!\nQuale vuoi eliminare? ");
scanf("%d", &elem);
cancellazione_elemento(Y, elem);
printf("Distruggiamo quindi l'albero creato per deallocare la memoria utilizzata!\n");
distruggi_albero(T);
}