[C] Cancellazione nodo da un albero

[Buzzz]

Io ho questo codice di un albero, in cui creo, inserisco valori e visualizzo l'albero..
ora devo fare la funziona "cancellazione", ma non saprei da dove iniziare.. volevo partire da una vecchia funzione "ricerca" che avevo, per poi ricavarne la cancellazione.. però già questa funziona poco.. infatti, se inserisco i seguenti valori:

-2 2 4 6 7

e poi ricerco il valore -2 (o addirittura 2), non me lo trova..

sapete aiutarmi intanto nel sistemare questa funzione "ricerca", e successivamente qualche consiglio o aiuto sulla "cancellazione"?

Grazie a tuttii,
Buona serata..

[Buzzz]

C'è qualche Buon'Anima disposta ad aiutarmi nella creazione della funzione CANCELLAZIONE?

Ne avrei assoluto bisogno a breve, qualche spunto ce l'ho in questo pezzo di codice, però non riesco ad andare avanti anche per il fatto di avere certi "errori" nell'esecione del codice..

La cancellazione la "estraggo" dalla funzione "Ricerca"

#include <stdio.h>
#include <stdlib.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);
    }
}

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

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 ricercare (cancellare):\t");
                    scanf("%d", &num);
                    ricerca(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                
                break;
            }
        }
    }
}

Grazie mille..

[ramy89]

Senza un pò di teoria non ce la fai, dai un' occhiata all' algoritmo della visita dfs e prova a implementarlo.

[Buzzz]

Io per esempio ho trovato un algoritmo:

7

4 10

2 6 8 12

[edit]:

7 -> 4 ( ->2 , ->6)
7 -> 10 ( ->8 , ->12)

tralasciando tutti gli altri casi, se io volessi eliminare per esempio la radice, posso scegliere due casi:

1) se scendo nel sottoalbero di sinistra, devo prendere la fogli più a destra che c'è, spostarla al posto della radice e cancellando infine la foglia;

2) se scendo nel sottoalbero di destra farò lo stesso procedimento, con la differenza che prendo la foglia più a sinistra che c'è;

il ragionamento non fa una piega ma tipo.. la funzione ricorsiva devo utilizzarla in questo caso? e se si, in quale procedimento e come?

non chiedo di farmi il codice, ma semplicemente un aiuto e/o consiglio su come svolgere il problema.. non fraintendetemi..

[ramy89]

Originariamente inviato da Buzzz
il ragionamento non fa una piega ma tipo.. la funzione ricorsiva devo utilizzarla in questo caso? e se si, in quale procedimento e come?

non chiedo di farmi il codice, ma semplicemente un aiuto e/o consiglio su come svolgere il problema.. non fraintendetemi..

Sul link che ti ho postato c'è l' algoritmo, scritto in pseudocodice.
Inizia a fare la funzione ricerca (ricorsiva); Visto che la cancellazione si basa sulla ricerca per ora preoccupati della dfs.

[Buzzz]

Avevo dato un occhio a quel link, ma sinceramente non ci ho capito molto sul funzionamento..

Ho comunque provato a buttar giù due righe di pseudo, per poi arrivare a questo codice che sembra funzionare (almeno teoricamente):

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

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

Però mi da questo errore:

assignment makes integer from pointer without a cast

in questa riga di codice:

p->dato = p->ptrsx;

Come mai?
Ho anche provato a fare una cosa del genere, ma da lo stesso identico errore..

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

[ramy89]

Originariamente inviato da Buzzz
p->dato = p->ptrsx;

p->dato è un intero, p->ptrsx è un puntatore a struct nodo.

nodo* eliminazione(nodo *p, int val) {
    nodo *r;
    r = p->dato;
    [...]

r è un puntatore a struct nodo, p->dato è un intero.

[Buzzz]

E come posso correggere questa incompatibilità di tipo di dato?

Cioè devo convertire r in un intero o viceversa..?

[ramy89]

Non serve a niente convertire, se il tuo scopo è leggere un intero dichiara un variabile di tipo int e leggilo.Se il tuo scopo è leggere un puntatore dichiara un puntatore a struct nodo e leggi quel puntatore.

[Buzzz]

Ho eliminato quel'if perché in fondo non mi sembrava fondamentale, almeno per adesso..

Ho compilato ed eseguito questo codice, ma al momento di cancellare mi da un errore:
Errore di segmentazione.

Ho controllato allora meglio il codice, ma non sono riuscito a trovare l'errore.. dove sbaglio?

#include <stdio.h>
#include <stdlib.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);
    }
}

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

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

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