[C] Cancellazione nodo da un albero

[ramy89]

Ci sono due problemi in queste due funzioni: non sempre hanno un valore di ritorno.
Se usi un if-else per gestire i valori di ritorno assicurati sempre che per ogni condizione ci può essere un valore di ritorno, altrimenti la funzione non termina mai.
Oppure più semplicemente, ritorni un valore solo alla fine della funzione e usi il costrutto if-else per settare il valore della variabile locale da ritornare:

nodo* eliminazione(nodo *p, int val) 
{
    if(p == NULL)
        return NULL;
    else
        elimina(p->ptrsx); // che indirizzo vuoi fare ritornare?
}

int elimina(nodo *p) 
{
    int num,risultato;
    
    if(p->ptrsx == NULL) 
    {
        num = p->dato;
        free(p);
        risultato=num;
    }
    else if(p->ptrsx != NULL)
    {
          risultato=elimina(p->ptrdx);
    }
    return risultato;
}

[Buzzz]

Ho modificato il codice come mi hai indicato, allora poi ho provato a ritornare p giusto per una prova, ma da sempre un errore oppure non cancella l'elemento.. ho provato a ritornare allora elimina, ma comunque da errore:

return makes pointer from integer without a cast

nodo* eliminazione(nodo *p, int val) {
    if(p == NULL)
        return NULL;
    else
        return elimina(p->ptrsx);
}

Da quello che ne deduco, penso ci sia un errore di ritorno perché provo a ritornare un intero..
Io però non ho ancora capito che valore dovrebbe tornare.. cioè di logica dovrebbe tornare p, però non ne capisco il perché e come allora filo ritornare, perché comunque mi da errore..

[Buzzz]

Ho provato anche così:

nodo* eliminazione(nodo *p, int val) {
    // if(p->dato == val)
        // p->dato = p->ptrsx;
    if(p == NULL)
        return NULL;
    else {
        elimina(p->ptrsx);
        return p;
    }
}

Ma la prima volta che inserisco il valore da cancellare non da errori, però non cancella l'elemento.. mentre la seconda volta da questo errore:

Albero(734) malloc: *** error for object 0x1007008a0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

O.o

[ramy89]

Perchè ritornare un intero?
Stai facendo confusione con i tipi, ma una cosa è importante: sapere da prima cosa deve fare quella funzione.
Tu hai fatto la funzione eliminazione che ritorna NULL nel caso il nodo considerato sia in realtà un puntatore a NULL.
Questo va bene perchè così chi chiama la funzione sa se ha avuto successo oppure no.
Ma non sai che valore far ritornare nel caso il nodo venga cancellato.
E' una cosa che va decisa prima di scrivere il codice della funzione, non dopo o durante.
Fossi in te allora gli farei ritornare un booleano: 0 se la funzione non ha avuto successo perchè il puntatore passato era NULL, 1 se il nodo è stato cancellato:

bool eliminazione(nodo *p, int val)   // includi stdbool.h
{  
    if(p == NULL)
        return false;
    else {
        elimina(p->ptrsx);
        true;
    }
}

Probabilmente quell' errore è dovuto che gli passi un puntatore a NULL, oppure un puntatore al nodo che hai appena cancellato, per cui non è più memoria allocata.

[Buzzz]

Ho importato e modificato il codice, compila correttamente, però mi da sempre lo stesso errore..

se tipo io inserisco: 2 - 4 - 7

e poi decido di cancellare il 7 per esempio, non da nessun errore;
però quando vado a "visitare" l'albero, l'elemento è ancora nell'albero, quindi non viene cancellato..
e se poi scelgo di cancellare un'altro valore, mi da l'ultimo errore che ho postato sopra, quello di 2 3 righe..

Il main non dovrebbe essere scorretto, in fondo ho preso quello della funzione "ricerca" e l'ho modificato..

L'unico dubbio mi viene nella funzione "elimina", siccome non ho ancora molta familiarità con le funzioni ricorsive..
Riusciresti a darci un occhio, per vedere se in fondo l'errore è in quella funzione?

Grazie mille, posto il codice attuale..

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

nodo* creazione(){
    nodo *q;
    q = malloc(sizeof(nodo));
    
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
    
    q->ptrsx = NULL;
    q->ptrdx = NULL;
    
    return q;
}

void ins_ord(nodo *p,nodo *q) {
    nodo *r;
    r = p;
    
    if(r->dato > q->dato) {
        if(r->ptrsx == NULL) {
            r->ptrsx = q;
        }else {
            ins_ord(r->ptrsx,q);
        }
    } else {
        if(r->ptrdx == NULL) {
            r->ptrdx = q;
        } else {
            ins_ord(r->ptrdx, q);
        }
    }
}

nodo* ins_bin(nodo *p) {
    nodo *q;
    q = creazione();
    
    if(p == NULL) {
        return q;
    } else {
        ins_ord(p, q);
    }
    
    return p;
}

void visita(nodo *p){
    nodo *r;
    r = p;
    
    if(r->ptrsx != NULL) {
        visita(r->ptrsx);
    }
    
    printf("%i", r->dato);
    printf("\t");
    
    if(r->ptrdx != NULL) {
        visita(r->ptrdx);
    }
}

bool eliminazione(nodo *p, int val) {
    // if(p->dato == val)
        // p->dato = p->ptrsx;
    if(p == NULL)
        return false;
    else {
        elimina(p->ptrsx);
        return true;
    }
}

int elimina(nodo *p) {
    int num, risultato;
    
    if(p->ptrsx == NULL) {
        num = p->dato;
        free(p);
        return num;
    } else if(p->ptrsx != NULL)
        risultato = elimina(p->ptrdx);
    
    return risultato;
}

int main() {
    nodo *radice = NULL;
    
    int scelta = 1, num;
    radice = NULL;
    
    while(scelta != 0) {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        
        switch(scelta) {
            case 1: {
                radice=ins_bin(radice);
                
                break;
            }
            case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                
                break;
            }
            case 3: {
                if(radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                
                break;
            }
        }
    }
}

[ramy89]

Non c'è da stupirsi che non cancella niente:

case 3: {
                if(radice != NULL){
                    printf("\nInserisci il numero da ricercare (cancellare):\t");
                    scanf("%d", &num);
                    ricerca(radice, num);

Cosa fa la ricerca?

void ricerca(nodo *p,int n) {
    if(p != NULL) {
        if(p->dato == n) printf("Il valore e' presente.\n\n");
        else printf("Il valore non e' presente.\n\n");
    }
}

[Buzzz]

In che senso la "ricerca"?
Io la funzione l'ho cancellata, non esiste più.. ho solo modificato il suo main in modo che richiami la funzione "eliminazione"..

[ramy89]

Guardavo ancora il main del codice vecchio
Prova così:

bool eliminazione(nodo *p, int val) {
    // if(p->dato == val)
        // p->dato = p->ptrsx;
    if(p == NULL)
        return false;
    else {
        elimina(p);   // parti dal primo nodo
        return true;
    }
}

Potrebbero anche esserci altre cose che non vanno, intanto prova così.

[Buzzz]

No, da sempre lo stesso identico errore..

La prima volta non da errore ma non cancella l'elemento, la seconda volta da questo errore:

Albero(344) malloc: *** error for object 0x1044008c0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

[ramy89]

L' ho corretto e ho notato principalmente due cose:
-A volte passi a considerare il nodo figlio (destro o sinistro) saltanto il padre.
Cioè chiami direttamente la funzione del figlio saltando il controllo su quel puntatore, che potrebbe benissimo puntare a NULL, causando segmentation fault;
-Gestisci l' albero usando i puntatori a NULL per capire quando un nodo è foglia, ma a volte non setti i valori dei nodi cancellati a NULL.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

int elimina(nodo** );

nodo* creazione(){
    nodo *q;
    q = malloc(sizeof(nodo));

    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");

    q->ptrsx = NULL;
    q->ptrdx = NULL;

    return q;
}

void ins_ord(nodo *p,nodo *q)
{
    nodo *r;
    r = p;
    if(r->dato > q->dato) {
        if(r->ptrsx == NULL) {
            r->ptrsx = q;
        }else {
            ins_ord(r->ptrsx,q);
        }
    } else {
        if(r->ptrdx == NULL) {
            r->ptrdx = q;
        } else {
            ins_ord(r->ptrdx, q);
        }
    }
}

nodo* ins_bin(nodo *p) {
    nodo *q;
    q = creazione();

    if(p == NULL) {
        return q;
    } else {
        ins_ord(p, q);
    }

    return p;
}

void visita(nodo *p){
    nodo *r;
    r = p;
    if(r!=NULL)
    {
        if(r->ptrsx != NULL) {    // controllare il padre
            visita(r->ptrsx);
        }

        printf("%i", r->dato);
        printf("\t");

        if(r->ptrdx != NULL) {
            visita(r->ptrdx);
        }
    }
}

bool eliminazione(nodo **p, int val)
{
    if((*p) == NULL)
        return false;
    else {
        elimina(p);
        return true;
    }
}

int elimina(nodo **p)
{
    int num, risultato;
    if((*p)!=NULL)
    {
        if((*p)->ptrsx == NULL)  
        {
            num = (*p)->dato;
            free(*p);
            *p=NULL;
            risultato=num;
        }
        else
        {
            risultato = elimina(&((*p)->ptrdx));
        }
    }
    return risultato;
}


int main()
{
    nodo *radice = NULL;
    int scelta = 1, num;
    while(scelta != 0) {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);

        switch(scelta) {
            case 1: {
                radice=ins_bin(radice);

                break;
            }
            case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");

                break;
            }
            case 3: {
                if(radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    radice->ptrsx=NULL;
                    radice->ptrdx=NULL;
                    eliminazione(&radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }

                break;
            }
        }
    }
}

Il motivo per cui ho messo dei doppi puntatori è che se nella funzione elimina ti capita di cancellare direttamente il primo nodo passato alla funzione, setti a NULL solo il puntatore di copia locale alla funzione elimina, che non è altro che una copia del puntatore originale.

Altre cose non vanno bene, ad esempio quando cancelli un nodo usi direttamente la free, non lo scambi con una foglia e cancelli solo quella foglia con la quale l' hai scambiato.
Ci potrebbe essere una perdita di memoria se ad esempio cancelli un nodo:

p indirizzo 1000
p->dato = 5
p->ptrsx = NULL
p->ptrdx = indirizzo 3000

s indirizzo 2000
p->dato = 10
p->ptrsx = NULL
p->ptrdx= NULL

Se cancelli il nodo p, il nodo s che è il figlio destro di p, viene perso, perchè non è più raggiungibile in nessun modo.Eppure quella memoria è allocata e non è mai stata liberata.