PDA

Visualizza la versione completa : [C++] Visita di un albero binario ordinato


il Principino
13-11-2011, 12:30
Salve :ciauz:
Dovrei implementare un programma che dato un albero binario ordinato,
lo visita in ampiezza(mediante coda) o profondità(mediante pila)
ho provato a scrivere il codice(prendendo in cosiderazione la visita in ampiezza, quindi mediante coda)


#include <iostream>
#include <stdlib.h>

using namespace std;

class albero
{
private:
int numero;
albero *sinistra;
albero *destra;

friend class coda;

public:
albero();
void set(int num) {numero=num;};
int get(){return numero;};
void pointsx(albero *point){sinistra=point;};
void pointdx(albero *point){destra=point;};
albero *getsx(){return sinistra;};
albero *getdx(){return destra;};
albero *inserisci(albero *temp, albero *nuovo);
void visualizza(albero *temp);
void BFS(albero *temp);
};

albero::albero()
{
numero=0;
sinistra=NULL;
destra=NULL;
}

albero *nuovo, *temp=NULL;

albero *albero::inserisci(albero *temp, albero *nuovo)
{
if(temp==NULL)
{
temp=nuovo;
}
else
{
if(nuovo->get() <= temp->get())
{
temp->pointsx(nuovo->inserisci(temp->getsx(), nuovo));
}
else
{
temp->pointdx(nuovo->inserisci(temp->getdx(), nuovo));
}
}
return (temp);
}

void albero::visualizza(albero *temp)
{
if(temp != NULL)
{
temp->visualizza(temp->getsx());
cout << temp->get() << " ";
temp->visualizza(temp->getdx());
}
}


void albero::BFS(albero *temp)
{
coda c ;
c.insert(temp);
while (!c.isEmpty())
{
temp=c.cancella();
while(temp!=NULL)
{c.insert(temp->getsx());
c.insert(temp->getdx());
}
}
}





///////////////////////

class coda
{
albero *temp;
albero *ultimo;
albero *nuovo;



public:
coda()
{
temp=NULL;
ultimo=NULL;
nuovo=NULL;
}

void insert(albero *nodo)
{
nuovo=new albero;
cout << "inizializzo il nodo ";
nuovo->set(nodo->get());
cout <<temp->get();
if(temp==NULL)
{temp=nuovo;
ultimo=nuovo;}
else
{ultimo->pointsx(nuovo);
ultimo=nuovo;}
}

void cancella()
{
albero *del;
del=temp;
temp=temp->getdx();
temp=temp->getsx();
delete del;
}

albero *isEmpty()
{
if(temp==NULL)
{return NULL;}
else
{return temp;}
}
};





int main()
{
int scelta, num;

do
{
cout<<"\n";
cout<<"################################################## ####################\n";
cout<<"# ALBERO BINARIO ORDINATO #\n";
cout<<"################################################## ####################\n";
cout<<"# Digita 1 per inserire un numero #\n";
cout<<"# Digita 2 per visualizzare l'albero ordinato #\n";
cout<<"# Digita 3 per visitare l'albero in ampiezza #\n";
cout<<"################################################## ####################\n";
cout<<"\nDigita la tua scelta-->";
cin >> scelta;

switch(scelta)
{
case 1:
nuovo=new albero;
cout << "\nInserisci un numero -> ";
cin >> num;
nuovo->set(num);
temp = nuovo-> inserisci(temp, nuovo);
system ("pause");
system ("cls");
break;

case 2:
if(temp==NULL)
{
cout << "\nNon ci sono elementi nell'albero";
system ("pause");
system ("cls");
break;
}
else
{
cout << "\nL'albero ordinato: \n";
temp->visualizza(temp);
cout<< "\n";
system ("pause");
system ("cls");
break;
}
case 3:
temp->BFS(temp);
system ("pause");
system ("cls");
break;


default:
cout << "\nINSERISCI UN VALORE CORRETTO\n\n";
break;
}
}while(scelta != 4);
return 0;
}




scusate se è pasticciato o trovate errori banali ma con il lavoro su altri tanti programmi in c++ su tipi dati e strutture sto perdendo la testa, e mi resta soltanto questo programma funzionante per poter affrontare l'esame.
Il compilatore da un errore ( aggregate `coda c' has incomplete type and cannot be defined ), ma ci sarà sicuramente da modificare o aggiungere sicuramente più di una cosa(ad esempio nelle funzioni della classe coda di insert e cancella non so come far puntare temp al prossimo elemento indifferentemente che sia a sx o dx, visto che non ho metodi del tipo getnext(), pointto , ma ho getsx(),getdx(),pointsx,pointdx).
In questo programma oltre alla classe albero, ho la classe coda, ma avevo provato a fare uno anche con una classa nodo e 2 friend class: albero e coda, ma avevo troppi problemi con tipi variabili ecc
voi che dite?? :stordita:

il Principino
14-11-2011, 17:57
nessuno? avrei tanto bisogno di una mano!
:( :(

il Principino
15-11-2011, 17:55
ho moficato il programma in questo modo:


#include <iostream>
#include <cstdlib>
using namespace std;

class albero
{
private:
int numero;
albero *sinistra;
albero *destra;
albero *prossimo;

friend class coda;

public:
albero();
void set(int num) {numero=num;};
int get(){return numero;};
void pointsx(albero *point){sinistra=point;};
void pointdx(albero *point){destra=point;};
albero *getsx(){return sinistra;};
albero *getdx(){return destra;};
void pointTo(albero *point){prossimo=point;}
albero *getnext(){return prossimo;}

albero *inserisci(albero *temp, albero *nuovo);
void visualizza(albero *temp);
void BFS(albero *temp);
};

class coda
{
albero *temp;
albero *ultimo;
albero *nuovo;



public:
coda();
void insert(albero *temp);
void cancella();
albero *isEmpty();
};

albero::albero()
{
numero=0;
sinistra=NULL;
destra=NULL;
}

albero *nuovo, *temp=NULL;

albero *albero::inserisci(albero *temp, albero *nuovo)
{
if(temp==NULL)
{
temp=nuovo;
}
else
{
if(nuovo->get() <= temp->get())
{
temp->pointsx(nuovo->inserisci(temp->getsx(), nuovo));
}
else
{
temp->pointdx(nuovo->inserisci(temp->getdx(), nuovo));
}
}
return (temp);
}

void albero::visualizza(albero *temp)
{
if(temp != NULL)
{
temp->visualizza(temp->getsx());
cout << temp->get() << " ";
temp->visualizza(temp->getdx());
}
}


void albero::BFS(albero *temp)
{
coda c ;
c.insert(temp);
while (c.isEmpty()!= NULL)
{
c.cancella();
if(temp!=NULL)
{c.insert(temp->getsx());
c.insert(temp->getdx());
}
}
}


coda::coda()
{
temp=NULL;
ultimo=NULL;
nuovo=NULL;
}

void coda::insert(albero *temp)
{
nuovo=new albero;
cout << "inizializzo il nodo ";
nuovo->set(temp->get());
cout <<temp->get();
if(temp==NULL)
{temp=nuovo;
ultimo=nuovo;}
else
{ultimo->pointTo(nuovo);
ultimo=nuovo;}

}

void coda::cancella()
{
albero *del;
del=nuovo;
temp=temp->getnext();
delete del;
}

albero *coda::isEmpty()
{
if(temp==NULL)
{return NULL;}
else
{return temp;}
}
int main()
{
int scelta, num;

do
{
cout<<"\n";
cout<<"################################################## ####################\n";
cout<<"# ALBERO BINARIO ORDINATO #\n";
cout<<"################################################## ####################\n";
cout<<"# Digita 1 per inserire un numero #\n";
cout<<"# Digita 2 per visualizzare l'albero ordinato #\n";
cout<<"# Digita 3 per visitare l'albero in ampiezza #\n";
cout<<"################################################## ####################\n";
cout<<"\nDigita la tua scelta-->";
cin >> scelta;

switch(scelta)
{
case 1:
nuovo=new albero;
cout << "\nInserisci un numero -> ";
cin >> num;
nuovo->set(num);
temp = nuovo-> inserisci(temp, nuovo);
system ("pause");
system ("cls");
break;

case 2:
if(temp==NULL)
{
cout << "\nNon ci sono elementi nell'albero";
system ("pause");
system ("cls");
break;
}
else
{
cout << "\nL'albero ordinato: \n";
temp->visualizza(temp);
cout<< "\n";
system ("pause");
system ("cls");
break;
}
case 3:
temp->BFS(temp);
system ("pause");
system ("cls");
break;


default:
cout << "\nINSERISCI UN VALORE CORRETTO\n\n";
break;
}
}while(scelta != 4);
return 0;
}




funziona, ma l'eseguibile si blocca nel momento in cui inizio la visita.
come mai?

oregon
15-11-2011, 22:55
Così costringi a copiare ed eseguire il programma, fare il debugging, ecc ... e magari nessuno ti risponde.

"L'eseguibile si blocca" non ha senso a meno che non indichi l'errore che hai (compreso di messaggio) e in quale linea ...

P.S. A grandi linee, mi sembra che nella insert di coda tu utilizzi il puntatore ultimo quando questo è NULL (in ultimo->pointTo(nuovo)) ... devi usare la new prima di utilizzare il puntatore ...

Loading