[C] - Eliminazione nodo albero binario.

[Saetta93]

Ciao a tuttii

Io ho questo codice, devo completare la/le funzione/i per eliminare un nodo da un albero binario, ma sono ad un punto in cui non riesco a continuare..

In pratica all'interno di questo if (da quello che ho capito):

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

dovrei salvare il contenuto della foglia, nel puntatore del nodo appena eliminato.. ma come devo fare?

Qualcuno può aiutarmi gentilmente?

Codice C:

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

Grazie mille a tutti

[Saetta93]

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?

[Varilion]

perchè setti

radice->ptrsx=NULL;
radice->ptrdx=NULL;

prima di chiamare "eliminazione(radice,val)" ?