Domanda Risolto Cancellare tutto l'albero c++

Stato
Discussione chiusa ad ulteriori risposte.
Ordina per data Ordina commenti per reazioni
S

Showme

Utente Silver
26 Settembre 2017
112
18
23
59
Salve ragazzi sono qui per chiedervi se potete darmi una mano con la funzione cancella albero.
C++: 
void cancella_albero(Albero &albero)
{
    if(albero == NULL) //Se sono dopo una foglia torno indietro
    {
        return;
    }
    if(albero->sx == NULL && albero->dx == NULL) // Se sono su una foglia cancello la foglia
    {
        delete albero;
    }
    else
    {
        cancella_albero(albero->sx); 
        cancella_albero(albero->dx);
    }
}

ho scritto questo codice ma non funziona, perché nel momento della ristampa entra in loop.
Qualcuno mi saprebbe dire dove sbaglio?
Grazie in anticipo
 
come prima cosa partiamo dal dire che stai confondendo reference e puntatori..
Albero& albero non può essere nullo , le reference se inizializzate con un puntatore nullo danno subito errore ancor prima del loro utilizzo..
ora non so se Albero sia una typedef di un puntatore tipo
typedef MyTree* Albero;
però da quello che vedo forse stai usando l'operatore sbagliato , se Albero infatti non è un typedef a puntatore ma direttamente una struct che ha due puntatori a oggetti di tipo Albero allora dovresti usare albero.sx e albero.dx....
oltretutto in cancella_albero(albero->dx) dovresti passare in realtà cancella_albero(*(albero.dx))
comunque tu fai due casi ma sbagliati.
quello in cui entrambi i puntatori sono nulli e l'else.
dovresti invece verificare singolarmente ogni puntatore per andare sul giusto...
if(albero.sx)
cancella_albero(*(albero.sx));

if(albero.dx)
cancella_albero(*(albero.dx));


posta comunque la definizione di tipo Albero.
 
Ultima modifica:
Ikarus_ ha detto:
come prima cosa partiamo dal dire che stai confondendo reference e puntatori..
Albero& albero non può essere nullo , le reference se inizializzate con un puntatore nullo danno subito errore ancor prima del loro utilizzo..
ora non so se Albero sia una typedef di un puntatore tipo
typedef MyTree* Albero;
però da quello che vedo forse stai usando l'operatore sbagliato , se Albero infatti non è un typedef a puntatore ma direttamente una struct che ha due puntatori a oggetti di tipo Albero allora dovresti usare albero.sx e albero.dx....
oltretutto in cancella_albero(albero->dx) dovresti passare in realtà cancella_albero(*(albero.dx))
comunque tu fai due casi ma sbagliati.
quello in cui entrambi i puntatori sono nulli e l'else.
dovresti invece verificare singolarmente ogni puntatore per andare sul giusto...
if(albero.sx)
cancella_albero(*(albero.sx));

if(albero.dx)
cancella_albero(*(albero.dx));


posta comunque la definizione di tipo Albero.
Clicca per espandere...

si perdonami, non ho postato tutto il codice, albero è una typedef (typedef nodo* albero) della struct nodo ovviamente.

posto il codice qua
C++: 
struct nodo{
    int data;
    nodo* sx;
    nodo* dx;
};

typedef nodo *Albero;

Albero crea_albero(Albero &albero, int numero)
{
    if(albero == NULL)
    {
        albero = new nodo;
        albero->data = numero;
        albero->sx = NULL;
        albero->dx = NULL;
    }
    else
    {
        if(albero->data >= numero)
        {
            crea_albero(albero->sx, numero);
        }
        else
        {
            crea_albero(albero->dx, numero);
        }
    }
    return (albero);
}

int main()
{
    vector<int> numeri ={4,5,6,8,1,3,6,5,2,4};
    Albero albero = NULL;

    for(size_t i=0; i<numeri.size();i++)
    {
        int numero = 0;
        numero = numeri[i];
        crea_albero(albero,numero);
    }

    cout << "Il tuo albero bilanciato e'" << endl;
    stampa_albero(albero);
    cout << endl;

    cout << endl;
    cout << "Inserisci il nodo da cercare" << endl;
    int ricercato;
    cin >> ricercato;

    if(trova_nodo(albero,ricercato))
    {
        cout << "Trovato" << endl;
    }
    else
    {
        cout << "Non trovato" << endl;
    }
    cout << endl;
  
    //qui ci dovrebbe essere la chiamata alla funzione che cancella tutto l'albero
return 0; 
}

inoltre ho provato a modificare la funzione cancella_albero in questo modo ma ancora nulla..

C++: 
void cancella_albero(Albero &albero)



{



    if(albero == NULL)



    {



        return;



    }



    if(albero->sx == NULL && albero->dx == NULL)



    {



        delete albero;



        return;



    }



        cancella_albero(albero->sx);



        cancella_albero(albero->dx);



}

ho semplicemente aggiunto un return e tolto l'else
 
va bene , ti consiglio per non capitare più nella tua vita in questo tipo di fraintendimenti di chiamare i typedef a puntatore con il prefisso LP o almeno solo P..
LPAlbero& pAlbero avrebbe permesso a chi legge di capire il codice senza nemmeno che tu dovessi postarlo..

comunque io cambierei in questo modo:
Codice: 
void cancella_albero(LPAlbero& pAlbero)
{
    if(pAlbero == NULL) //Se sono dopo una foglia torno indietro
    {
        return;
    }
    
    if(pAlbero->sx)
        cancella_albero(pAlbero->sx);
    
    if(pAlbero->dx)
        cancella_albero(pAlbero->dx);
}

se ancora ti looppa sul print allora forse l'errore in realtà non è qui...
posta come imposti il print di tutti i nodi
 
Ikarus_ ha detto:
va bene , ti consiglio per non capitare più nella tua vita in questo tipo di fraintendimenti di chiamare i typedef a puntatore con il prefisso LP o almeno solo P..
LPAlbero& pAlbero avrebbe permesso a chi legge di capire il codice senza nemmeno che tu dovessi postarlo..

comunque io cambierei in questo modo:
Codice: 
void cancella_albero(LPAlbero& pAlbero)
{
    if(pAlbero == NULL) //Se sono dopo una foglia torno indietro
    {
        return;
    }
   
    if(pAlbero->sx)
        cancella_albero(pAlbero->sx);
   
    if(pAlbero->dx)
        cancella_albero(pAlbero->dx);
}

se ancora ti looppa sul print allora forse l'errore in realtà non è qui...
posta come imposti il print di tutti i nodi
Clicca per espandere...

il print dovrebbe essere corretto, perché quando eseguo la stampa iniziale dell'albero funziona correttamente, comunque riguardo al tuo cambiamento vorrei chiederti una cosa.
Non vedo l'istruzione per cancellare il nodo, dove la dovrei mettere?
E inoltre, quel if(pAlbero->sx) significa per caso "se esiste un figlio sinistro?".
grazie
 
si hai ragione manca un ultima istruzione , che però è da mettere a fine check e non all'inizio (come nel tuo listato) mea culpa
Codice: 
void cancella_albero(LPAlbero& pAlbero)
{
    if(pAlbero == NULL) //Se sono dopo una foglia torno indietro
    {
        return;
    }
   
    if(pAlbero->sx)
        cancella_albero(pAlbero->sx);
   
    if(pAlbero->dx)
        cancella_albero(pAlbero->dx);
   
    delete(pAlbero);
}

ps: i due if servono a verificare che effettivamente il nodo su cui sei ha child , verificati singolarmente se esistono vengono eliminati
 
Ikarus_ ha detto:
si hai ragione manca un ultima istruzione , che però è da mettere a fine check e non all'inizio (come nel tuo listato) mea culpa
Codice: 
void cancella_albero(LPAlbero& pAlbero)
{
    if(pAlbero == NULL) //Se sono dopo una foglia torno indietro
    {
        return;
    }
  
    if(pAlbero->sx)
        cancella_albero(pAlbero->sx);
  
    if(pAlbero->dx)
        cancella_albero(pAlbero->dx);
  
    delete(pAlbero);
}

ps: i due if servono a verificare che effettivamente il nodo su cui sei ha child , verificati singolarmente se esistono vengono eliminati
Clicca per espandere...

Nulla continua ad andare in loop, ti posto l'intero codice magari ho sbagliato qualcosa
C++: 
#include <iostream>
#include <vector>

using namespace std;

struct nodo{
    int data;
    nodo* sx;
    nodo* dx;
};

typedef nodo *Albero;


Albero crea_albero(Albero &albero, int numero)
{
    if(albero == NULL)
    {
        albero = new nodo;
        albero->data = numero;
        albero->sx = NULL;
        albero->dx = NULL;
    }
    else
    {
        if(albero->data >= numero)
        {
            crea_albero(albero->sx, numero);
        }
        else
        {
            crea_albero(albero->dx, numero);
        }
    }
    return (albero);
}

bool trova_nodo(Albero albero, int ricercato)
{
    if(albero == NULL)
    {
        return false;
    }
    if(albero->data == ricercato)
    {
        return true;
    }
    else
    {
        return (trova_nodo(albero->sx,ricercato)|| trova_nodo(albero->dx,ricercato));
    }
}

void cancella_albero(Albero &albero)
{
    if(albero == NULL)
    {
        return;
    }
    if(albero->sx)
    {
        cancella_albero(albero->sx);
    }
    if(albero->dx)
    {
        cancella_albero(albero->dx);
    }
    delete albero;
}


void stampa_albero(Albero albero)
{
    if(albero != NULL)
    {
         cout << albero->data << " ";
         stampa_albero(albero->sx);
         stampa_albero(albero->dx);
    }
}

void nodi_livelli_pari(Albero albero, int depth, vector<int> &livello)
{
    if(albero == NULL)
    {
        return;
    }
    if(depth%2 == 0 && depth != 0)
    {
        livello.push_back(albero->data);

    }
        nodi_livelli_pari(albero->sx,depth+1,livello);
        nodi_livelli_pari(albero->dx,depth+1,livello);
}

int main()
{
    vector<int> numeri ={4,5,6,8,1,3,6,5,2,4};
    Albero albero = NULL;

    for(size_t i=0; i<numeri.size();i++)
    {
        int numero = 0;
        numero = numeri[i];
        crea_albero(albero,numero);
    }

    cout << "Il tuo albero bilanciato e'" << endl;
    stampa_albero(albero);
    cout << endl;

    cout << endl;
    cout << "Inserisci il nodo da cercare" << endl;
    int ricercato;
    cin >> ricercato;

    if(trova_nodo(albero,ricercato))
    {
        cout << "Trovato" << endl;
    }
    else
    {
        cout << "Non trovato" << endl;
    }
    cout << endl;

    //int depth = 0;

    cancella_albero(albero);


    cout << "Il tuo albero ora e'" << endl;
    stampa_albero(albero);

    cout << endl;

    /*vector<int> livello;

    nodi_livelli_pari(albero,depth,livello);

    for(size_t i=0; i<livello.size(); i++)
    {
        cout << livello[i] << " ";
    }*/

    return 0;
}

tralascia le altre funzioni, stavo creando un pò di funzioni base per allenarmi
 
provo a perdere un pò di tempo vediamo se riesco a farti capire qualcosa in più..
C++: 
Albero crea_albero(Albero &albero, int numero)
{
    if(albero == NULL)
    {
        albero = new nodo;
        albero->data = numero;
        albero->sx = NULL;
        albero->dx = NULL;
    }
    else
    {
        if(albero->data >= numero)
        {
            crea_albero(albero->sx, numero);
        }
        else
        {
            crea_albero(albero->dx, numero);
        }
    }
    return (albero);
}

nel listato di sopra c'è un errore di fondo... ovvero se tu passi il puntatore come reference di un puntatore non serve che ritorni il puntatore a fine metodo.. questo perchè le reference vanno a modificare direttamente il puntatore che tu passi al metodo (invece di farne uno nuovo con uguale valore).
Quindi puoi passare il metodo come void invece di ritornare il puntatore che hai passato come reference.

comunque il problema per cui non si ferma nel printare i dati è che non abbiamo portato a null il puntatore , svista davvero stupida (io sono stupido) :)
nuovo metodo cancella albero:

C++: 
void cancella_albero(Albero &albero)
{
    if(albero == NULL)
    {
        return;
    }
  
    cout << "elimino l'albero 0x" << albero << endl;
  
    if(albero->sx)
    {
        cancella_albero(albero->sx);
    }
  
    if(albero->dx)
    {
        cancella_albero(albero->dx);
    }
  
    delete albero;
    albero = NULL;
}

non portare a NULL il puntatore comporta che il puntatore continua a puntare su memoria non più allocata..
il puntatore altro non è che un numero (occupa due byte nella maggior parte delle architetture quindi è qualcosa di simile a un unsigned short)
se non lo porti a NULL (che sarebbe 0) il suo valore continua ad essere quello di un indirizzo di memoria (ad esempio 0x736476) che continuerà a != NULL , quindi nel tuo check if(albero == NULL) in stampa_albero l'if non sarebbe stato true ma false
 
  • Mi piace
Reazioni: Showme
Ikarus_ ha detto:
provo a perdere un pò di tempo vediamo se riesco a farti capire qualcosa in più..
C++: 
Albero crea_albero(Albero &albero, int numero)
{
    if(albero == NULL)
    {
        albero = new nodo;
        albero->data = numero;
        albero->sx = NULL;
        albero->dx = NULL;
    }
    else
    {
        if(albero->data >= numero)
        {
            crea_albero(albero->sx, numero);
        }
        else
        {
            crea_albero(albero->dx, numero);
        }
    }
    return (albero);
}

nel listato di sopra c'è un errore di fondo... ovvero se tu passi il puntatore come reference di un puntatore non serve che ritorni il puntatore a fine metodo.. questo perchè le reference vanno a modificare direttamente il puntatore che tu passi al metodo (invece di farne uno nuovo con uguale valore).
Quindi puoi passare il metodo come void invece di ritornare il puntatore che hai passato come reference.

comunque il problema per cui non si ferma nel printare i dati è che non abbiamo portato a null il puntatore , svista davvero stupida (io sono stupido) :)
nuovo metodo cancella albero:

C++: 
void cancella_albero(Albero &albero)
{
    if(albero == NULL)
    {
        return;
    }
 
    cout << "elimino l'albero 0x" << albero << endl;
 
    if(albero->sx)
    {
        cancella_albero(albero->sx);
    }
 
    if(albero->dx)
    {
        cancella_albero(albero->dx);
    }
 
    delete albero;
    albero = NULL;
}

non portare a NULL il puntatore comporta che il puntatore continua a puntare su memoria non più allocata..
il puntatore altro non è che un numero (occupa due byte nella maggior parte delle architetture quindi è qualcosa di simile a un unsigned short)
se non lo porti a NULL (che sarebbe 0) il suo valore continua ad essere quello di un indirizzo di memoria (ad esempio 0x736476) che continuerà a != NULL , quindi nel tuo check if(albero == NULL) in stampa_albero l'if non sarebbe stato true ma false
Clicca per espandere...


Perfetto ho capito, ho anche provato a impostare la funzione come void e ho capito il procedimento.
Grazie mille dell'aiuto come sempre ;D
 
figurati , si vede che ti stai mettendo sotto quindi meriti il sostegno , diversamente ad esempio da qualcuno che pochi giorni fa ha aperto una discussione giusto per chiedere un pò di codice , cosi per non sporcarsi nemmeno le mani ahah..
non so se stai chiudendo le discussione che apri però... dovresti chiuderle una volta risolto.
 
Grazie :D
Ero convinto che cambiando lo stato in risolto fosse come averla chiusa.. colpa mia.
Per chiuderla basta fare "smetti di seguire"?
 
vai in sezione C/C++ senza entrare in nessuna discussione... in alto a destra dovresti trovare un pannellino che ti permette di amministrare le discussione di cui sei autore. Da quel pannellino seleziona "chiudi discussioni selezionate" e dopo di chè seleziona la discussione da chiudere (il quadratino fianco al nome) e poi fai "applica azioni".
Attenzione : sinceramente sarà un anno che non apro una discussione quindi non ricordo precisamente il funzionamento ma sopratutto potrebbe tranquillamente essere cambiato...
 
Ikarus_ ha detto:
vai in sezione C/C++ senza entrare in nessuna discussione... in alto a destra dovresti trovare un pannellino che ti permette di amministrare le discussione di cui sei autore. Da quel pannellino seleziona "chiudi discussioni selezionate" e dopo di chè seleziona la discussione da chiudere (il quadratino fianco al nome) e poi fai "applica azioni".
Attenzione : sinceramente sarà un anno che non apro una discussione quindi non ricordo precisamente il funzionamento ma sopratutto potrebbe tranquillamente essere cambiato...
Clicca per espandere...

edit, ho provato a fare smetti di seguire ma nulla, il pannellino di amministrazione non riesco a vederlo (o sono io che non ci vedo più o sicuramente avranno impostato un altro modo per chiudere)
 
Stato
Discussione chiusa ad ulteriori risposte.

DISCUSSIONI SIMILI

C
Domanda aiuto programma
  • 8
  • 505
8
505
C / C++
CyberBerry
L
Domanda Programma di gestione autostrada in C
  • 1
  • 363
1
363
C / C++
DispatchCode
D
Guida Calcolare la lunghezza in bytes di una funzione in C/C++ e difficoltà varie
  • 5
  • 627
5
627
C / C++
JunkCoder
M
Risolto Verifica forma, dominio e utente di una email, bloccato nel creare un loop.
  • 1
  • 388
1
388
Python
mrcamarium
H
Assistente virtuale: come migliorarlo, come cambiare la sua voce, come renderlo piu veloce, e magari come integrare un api key (gia provato non va)
  • 6
  • 453
6
453
Il tuo Software
--- Ra ---
Top Bottom
Indietro