PDA

Visualizza la versione completa : [C++] Albero binario


pakylory
18-07-2003, 19:57
Salve,
ho bisogno di un vostro aiuto...
Sono alle prime armi con questo tipo di strutture; mi chiedevo se qualcuno potrebbe farmi vedere il codice per risolvere questo quesito cos da poterlo studiare bene bene.

Dato un albero i cui nodi contengono valori interi, scrivere gli operatori tipici di tale struttura: l'inserimento e la cancellazione di una foglia ed elencare i valori contenuti nei nodi effettuando una visita in ampiezza.
Il prog. va implementato attraverso le classi.

Grazie a coloro che sapranno aiutarmi.....
:ciauz: :ciauz:

pakylory
19-07-2003, 09:06
#include<iostream.h>
#include<stdlib.h>
//creazione classe...
class albero
{
private:
class ele_albero
{
private:
ele_albero *p_alb_sin;
ele_albero *p_alb_des;
public:
int dato;
friend class albero;
};
public:
ele_albero *p_iniz;

albero::albero()
{
p_iniz = NULL;
}

//Funzioni pubbliche...
albero::ele_albero *albero::inserisci(ele_albero *p_iniz, int num);
void albero::visualizza(ele_albero *p_iniz);
void albero::elimina_foglia(ele_albero *p_iniz);
};


//Funzione di inserimento dati...
albero::ele_albero *albero::inserisci(ele_albero *p_iniz, int num)
{
ele_albero *p = p_iniz;

if(p == NULL)
{
p = new ele_albero;
p->dato = num;
p->p_alb_sin = NULL;
p->p_alb_des = NULL;
}
else
{
if(num < p->dato)
p->p_alb_sin = inserisci(p->p_alb_sin, num); //visita sottoalbero sinistro
else if(num > p->dato)
p->p_alb_des = inserisci(p->p_alb_des, num); //visita sottoalbero destro
}
return p;
}


//Funzione di visualizzazione degli elementi dell'albero...
void albero::visualizza(ele_albero *p_iniz)
{
ele_albero *p = p_iniz;

if(p != NULL)
{
cout<<p->dato<<" ";
visualizza(p->p_alb_sin); //visita sottoalbero sinistro
visualizza(p->p_alb_des); //visita sottoalbero destro
}
}

//Questa funzione cerca tutte le foglie dell'albero e, se l'utente vuole, le
//pu cancellare...
void albero::elimina_foglia(ele_albero *ptr_iniz)
{
ele_albero *ptr_sin, *ptr_des;
ptr_sin = ptr_iniz->p_alb_sin;
ptr_des = ptr_iniz->p_alb_des;

if(ptr_sin == NULL && ptr_des == NULL) // un solo nodo
{
delete p_iniz;
p_iniz = NULL;
cout<<"ELIMINATA RADICE!! ALBERO VUOTO!!\n\n";
}


char risp;
//ramo sinistro
if (ptr_sin != NULL)
if (ptr_sin->p_alb_sin == NULL && ptr_sin->p_alb_des == NULL)
{
cout<<"Trovata foglia: "<<ptr_sin->dato<<". Cancellare?";
cin>>risp;
if(risp=='s')
{
delete ptr_sin;
ptr_iniz->p_alb_sin=NULL;
}
}
else
elimina_foglia(ptr_sin);

//ramo destro
if (ptr_des != NULL)
if (ptr_des->p_alb_sin == NULL && ptr_des->p_alb_des == NULL)
{
cout<<"\nTrovata foglia: "<<ptr_des->dato<<". Cancellare?";
cin>>risp;
if(risp == 's')
{
delete ptr_des;
ptr_iniz->p_alb_des = NULL;
}
}
else
elimina_foglia(ptr_des);
}



void main()
{
int scelta, num;
albero tree;

do
{
cout<<"\n\n\t\t\t GESTIONE ALBERO\n";
cout<<"\n\n\t Digita il numero corrispondente alla funzione da eseguire\n";
cout<<"\n\n1. Inserisci elemento;\n";
cout<<"\t\t\t\t\t\t 2. Elimina elemento;\n";
cout<<"\n3. Visualizza albero;\n";
cout<<"\t\t\t\t\t\t 0. Termina esecuzione;\n";
cout<<"\n\t\t\t FAI LA TUA SCELTA: ";
cin>>scelta;
cout<<"\n";



switch(scelta)
{

case 1: {
do
{
cout<<"\n\n\t\tInserisci elemento (0 per terminare): ";
cin>>num;
if(num != 0)
//attivazione funzione "inserisci"...
tree.p_iniz = tree.inserisci(tree.p_iniz, num);
}
while(num != 0);
cout<<"\n\n";
system("PAUSE");
break;
}


case 2: {
//attivazione funzione "elimina_foglia"...
tree.elimina_foglia(tree.p_iniz);
cout<<"\n\nL'ALBERO RISULTA COSI' COMPOSTO: ";
//attivazione funzione "visualizza"...
tree.visualizza(tree.p_iniz);
cout<<"\n\n";
system("PAUSE");
break;
}

case 3: {
cout<<"\n\nL'ALBERO RISULTA COSI' COMPOSTO: ";
//attivazione funzione "visualizza".
tree.visualizza(tree.p_iniz);
cout<<"\n\n";
system("PAUSE");
break;
}
}
}
while(scelta != 0);
}


Ho trovato questo codice! Secondo voi va bene???

pakylory
19-07-2003, 16:36
Originariamente inviato da pakylory


//Questa funzione cerca tutte le foglie dell'albero e, se l'utente vuole, le
//pu cancellare...
void albero::elimina_foglia(ele_albero *ptr_iniz)
{
ele_albero *ptr_sin, *ptr_des;
ptr_sin = ptr_iniz->p_alb_sin;
ptr_des = ptr_iniz->p_alb_des;

if(ptr_sin == NULL && ptr_des == NULL) // un solo nodo
{
delete p_iniz;
p_iniz = NULL;
cout<<"ELIMINATA RADICE!! ALBERO VUOTO!!\n\n";
}


char risp;
//ramo sinistro
if (ptr_sin != NULL)
if (ptr_sin->p_alb_sin == NULL && ptr_sin->p_alb_des == NULL)
{
cout<<"Trovata foglia: "<<ptr_sin->dato<<". Cancellare?";
cin>>risp;
if(risp=='s')
{
delete ptr_sin;
ptr_iniz->p_alb_sin=NULL;
}
}
else
elimina_foglia(ptr_sin);

//ramo destro
if (ptr_des != NULL)
if (ptr_des->p_alb_sin == NULL && ptr_des->p_alb_des == NULL)
{
cout<<"\nTrovata foglia: "<<ptr_des->dato<<". Cancellare?";
cin>>risp;
if(risp == 's')
{
delete ptr_des;
ptr_iniz->p_alb_des = NULL;
}
}
else
elimina_foglia(ptr_des);
}



Scusate ragazzi ma ho un problema con il codice su riportato!!!
Non si riesce ad eliminare l'ultimo dato ovvero la radice, come mai???
Per favore rispondete :(
:ciauz:

alexfin
24-07-2003, 17:10
ok prima di tutto qualche errore di fondo.
Hai dichiarato il puntatore alla radice come pubblico !!! Non dovevi ! quel puntatore chiaramente un dato privato, serve solo ai metodi della classe stessa, e va inizializzato nel costruttore come tu giustamente hai fatto, altrimenti addio programmazione a oggetti !!! Ti immagini cosa succederebbe se un cliente modificasse (e lo pu fare dato che pubblico) quel puntatore? l'intero albero si perderebbe nel nulla!
ele_albero non dovrebbe essere una classe (non ha metodi!) ma una semplice struct! il che oltretutto evita quella bruttura di friend, che sporca il codice ed un'altra violazione inutile del paradigma a oggetti (come usare un goto in programmazione strutturata)
Come conseguenza a quello che ho detto prima, nessun metodo che operi sull'albero (inserimenti, ricerche, cancellazioni, visite ecc ecc) deve avere come argomento il puntatore all'albero!!! A che serve??? Ovviamente per fare ricorsioni ti devi appoggiare su funzioni ausiliarie (private !!!)

Ad esempio, un semplice metodo che cerca le foglie :
// questa pubblica
void Albero::cerca_foglie()
{
rec_cerca_foglie( root_pointer );
}
//questa privata !
void Albero::rec_cerca_foglie( ele_albero * ele )
{
if ( ele->left ) rec_cerca_foglie( ele->left ); // c' un figlio sx, ricorri a sx
if ( ele->right ) rec_cerca_foglie( ele->right); // c' un figlio dx, ricorri a dx
if ( (ele->left == NULL) && (ele->right == NULL) ) std::cout << "Foglia, valore : " << ele->value << std::endl ;
// non ci sono figli, quindi una foglia e scrive il valore
}
Il tuo algoritmo di cancellazione delle foglie a prima vista mi sembra vada bene, riscrivi il codice seguendo i suggerimenti; ti sar sfuggito qualcosa...

PS quello che hai implementato tu un albero binario di ricerca, i problemi con queste strutture arrivano quando li devi bilanciare!!! E in effetti un albero sbilanciato abbastanza inutile...

pakylory
24-07-2003, 19:16
Ti ringrazio mille alexfin per la tua dettagliata spiegazione....
Sai, sono alle prime armi con gli alberi, quello su riportato non l'ho fatto io ma l'ho trovato...
Sapevo che c'era qualcosina che non andava; studiando da "La guida completa" di H. Schildt mi ero gi accorto che il FRIEND non viene quasi mai utilizzato!

Grazie ancora, ora mi metto a lavoro per imparare questi alberi...

:ciauz: :ciauz:

Loading