[C] Cancellazione nodo da un albero

[Buzzz]

Non ho capito bene se il codice postato è quello funzionante, o se devo sistemarlo o vedere delle cose.. perché l'ho provato, però se io inserisco ad esempio 3 numeri qualsiasi e poi tento di eliminarne uno.. sia che inserisco un numero dell'albero e sia che inserisco un numero che non esiste, la funzione mi elimina tutti gli elementi dell'albero..

E' probabile che l'errore sia nella funzione ricorsiva? O magari è quando la free?

[ramy89]

C'è da correggere le cose che ti ho detto nell' altro post, a partire da "Altre cose non vanno bene, ad esempio quando ..." .

[Buzzz]

Penso di aver capito cosa devo fare..
a.. prima di utilizzare la free, dovrei salvare il contenuto della foglia da spostare per poi "sostituirla" al nodo cancellato, giusto?
Ma questa operazione non la faccio già nel secondo if della funzione elimina, con questa riga: num = (*p)->dato;?

E quella & davanti a (*p)->ptrdx, dentro alla ricorsione, cosa significa?

[ramy89]

Originariamente inviato da Buzzz
Penso di aver capito cosa devo fare..
a.. prima di utilizzare la free, dovrei salvare il contenuto della foglia da spostare per poi "sostituirla" al nodo cancellato, giusto?
Ma questa operazione non la faccio già nel secondo if della funzione elimina, con questa riga: num = (*p)->dato;?

Ma tu non cambi i valori di alcun nodo, salvi solo il valore senza scriverlo da nessuna parte.
Fai prima una ricerca per trovare una qualsiasi foglia e scambia il valore del nodo da cancellare con quella foglia.
Poi elimini quella foglia.
Tra l' altro se devi eliminare un nodo foglia la funzione diventa molto più semplice perchè non devi effettuare alcuna chiamata ricorsiva.

E quella & davanti a (*p)->ptrdx, dentro alla ricorsione, cosa significa?

Ho cambiato i parametri della funzione e p non è più un puntatore a nodo,ma un puntatore a puntatore a nodo.
L' espressione (*p)->ptrdx restituisce il valore del puntatore che punta al nodo figlio destro di *p.
la funzione elimina prende come parametro un puntatore a puntatore, per cui con & sto prendendo l' indirizzo di quel puntatore, quindi sto passando come parametro un puntatore a puntatore.

[Buzzz]

Il problema mi sembra sia nel secondo if della funzione elimina, cioè questo:

if((*p)->ptrsx == NULL)  
{
            num = (*p)->dato;
            free(*p);
            *p=NULL;
            
            risultato=num;
}

Correggimi se erro, ma io ho capito questo..

1- salvo in una variabile intera, il valore a cui punta p
2- libero il puntatore p
3- elimino il puntatore p (quindi perdo il valore a cui si riferisce p)
[ 4- alla fine ritorno il valore che nei punti 2 e 3 avevo cancellato ]

Ora io dovrei prendere questo valore salvato in num, e salvarlo dentro a p..
Però come devo fare?

Cioè, se io utilizzo una cosa del genere mi da errore di cast, sia che io utilizzi l'* e sia che io non lo utilizzi:

if((*p)->ptrsx == NULL)  
{
            num = (*p)->dato;
            free(*p);
            *p=NULL;
            
            *p = num;
            
            risultato=num;
}

Eppure mi sembra la soluzione più sensata e corretta, almeno teoricamente..
Dorei invece salvare a inizio funzione l'indirizzo di p in r, così poi nella if salvo num in r.. può essere una soluzione?

[Buzzz]

Ho provato anche salvando p in r, ma l'errore è sempre lo stesso..
Quindi forse non è la soluzione più corretta la mia..

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

Ma.. non è che magari l'errore sia da un'altra parte? Anche se a me non sembra..

[ramy89]

Io applicherei un' approcio più procedurale:
-Funzione che ritorna l' indirizzo della prima foglia che trova.
-Funzione per scambiare il valore di due nodi;
-Funzione per eliminare una foglia.

Nell' ultima hai bisogno di passare un puntatore a puntatore per settare il valore del puntatore al nodo foglia a NULL.

Edit:
Solito errore, non confondere i puntatori con gli interi:

*r = num;

num è un intero, r è un puntatore a puntatore a nodo, *r è un puntatore a nodo.
Inizia per gradi, facendo una funzione swap:

void swap(nodo* a, nodo* b);

Effetto: scambia i valori dei due nodi (cioè il campo dato).Poi passi alle altre due.

[Buzzz]

Io quindi dovrei creare altre 3 "semplici" (di poche righe) funzioni, dove svolgo questi 3 punti?

Con una cosa simile a questa, dove poi magari, all'interno del secondo if, salvo num in r?:

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

[Buzzz]

Con un amico sono arrivato a questo codice:

#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){
    if(p != NULL){
        visita(p->ptrsx);
        printf("%i\t", p->dato);
        visita(p->ptrdx);
    }
}

bool eliminazione(nodo *p,int val){
    nodo *rd,*rs;
    if(p==NULL) return false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        free(p);
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rd->ptrsx=rs;
            p=rd;
        }
        return true;
    }else if (val > p->dato) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}

//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo *p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        free(p);
        p=NULL;
    }
}

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;
            }
        }
    }
}

Però qualsiasi numero io voglia cancellare (sia che esista, e sia che non esista), mi elimina sempre la radice, ovvero il primo valore che inserisco nell'albero..

Come mai?

[ramy89]

Però qualsiasi numero io voglia cancellare (sia che esista, e sia che non esista), mi elimina sempre la radice, ovvero il primo valore che inserisco nell'albero..

Come mai?

eliminazione(radice, num);

Chissà come mai