PDA

Visualizza la versione completa : [c++]calcolo profonditÓ


9178angel
04-09-2004, 20:04
#include <iostream.h>
#include <stdlib.h>
#define MAX 100

class albero
{
albero *dx,*sx,*prec;
public: int valore;
albero(void);
~albero(void);
void nuovo(albero *nodo, albero *start);
void crea(albero *inizio);
void visualizza1(albero *pNodo); //lettura preordine
void visualizza2(albero *pNodo); //lettura inordine
void visualizza3(albero *pNodo); //lettura post ordine
void cancella(albero *pNodo, int kappa);
};

/* Dichiarazione costruttore */
albero::albero()
{
dx=NULL;
sx=NULL;
prec=NULL;
};

/* Dichiarazione distruttore */
albero::~albero()
{
dx=NULL;
sx=NULL;
prec=NULL;
};

/* dichiarazione funzione crea */
void albero::crea (albero *inizio)
{
char ris;
albero *NewThree;

cout << inizio->valore << " ha un figlio sinistro? ( Y / N ) " << endl;
cin >> ris;
cout << endl;
if (ris=='Y' || ris=='y')
{
NewThree= new albero;
inizio->sx=NewThree;
nuovo (NewThree,inizio);

} // end if
else
inizio->sx=NULL;

cout << inizio->valore << " ha un figlio destro? ( Y / N ) " << endl;
cin >> ris;
cout << endl;
if (ris=='Y' || ris=='y')
{
NewThree= new albero;
inizio->dx=NewThree;
nuovo (NewThree,inizio);

} // end if
else
inizio->dx=NULL;
}; // end crea

/* Dichairazione funzione visualizza per la stampa preordine*/
void albero::visualizza1(albero *pNodo)
{

if (pNodo != NULL)
{
cout << pNodo->valore << " ";
visualizza1 (pNodo->sx);
visualizza1 (pNodo->dx);
}
};

/* Dichairazione funzione visualizza per la stampa inordine*/
void albero::visualizza2(albero *pNodo)
{

if (pNodo != NULL)
{
visualizza2 (pNodo->sx);
cout << pNodo->valore << " ";
visualizza2 (pNodo->dx);
}
};

/* Dichairazione funzione visualizza per la stampa postordine*/
void albero::visualizza3(albero *pNodo)
{
if (pNodo != NULL)
{
visualizza3 (pNodo->sx);
visualizza3 (pNodo->dx);
cout << pNodo->valore << " ";
}
};

/* Dichiarazione della funzione nuovo */
void albero::nuovo(albero *nodo, albero *inizio)
{
int i=0;
int valore [MAX];

nodo->prec=inizio;
cout << "Inserire il valore del nodo: ";
cin >> valore[i];
cout << endl;
nodo->valore=valore[i];
i++;
crea(nodo);
};

void albero::cancella(albero *pNodo, int kappa)
{
albero *precedente,*prec2;
int somma,flag=0;
if ((pNodo->sx) && (pNodo->dx))
{
cancella((pNodo->sx) ,kappa);
cancella((pNodo->dx) ,kappa);
}
else if ((pNodo->sx))
{
cancella((pNodo->sx) ,kappa);
}
else if (pNodo->dx)
{
cancella(pNodo->dx ,kappa);
}
else
{
precedente=pNodo->prec;
somma=((precedente->valore) +(pNodo->valore));

if (somma==kappa)
{
//la radice non punta + alla foglia
precedente->sx=NULL;

//se non si tratta del nodo radice
if(precedente->prec)
{
//si cancella il puntatore della radice alla radice stessa
prec2= precedente;
precedente = precedente->prec;
if (precedente->sx == prec2)
precedente->sx=NULL;

}
}
}
};

int main()
{
albero *Three;
int babbo,kappa,scelta;

cout << "Inserisci il valore del nodo radice : ";
cin >> babbo;
Three= new albero;
Three->valore=babbo;
cout << endl;
Three->crea(Three);
cout << endl << endl;
system ("PAUSE");
system ("CLS");

cout << "SCEGLI IL TIPO DI VISUALIZZAZIONE DELL'ALBERO" << endl
<< " 1- PREORDINE " << endl
<< " 2- INORDINE " << endl
<< " 3- POSTORDINE " << endl << endl;
cin >> scelta;
cout << endl << endl;

switch (scelta)
{
case 1:
cout << "Questa e' la lettura dell'albero utilizzando un attraversamento in preordine " << endl << endl;
Three->visualizza1(Three);
break;
case 2:
cout << "Questa e' la lettura dell'albero utilizzando un attraversamento in inordine " << endl << endl;
Three->visualizza2(Three);
break;
case 3:
cout << "Questa e' la lettura dell'albero utilizzando un attraversamento in postordine " << endl << endl;
Three->visualizza3(Three);
break;
default:
cout << " Scelta non valida: numero sconosciuto!!!" << endl << endl;
}
cout << endl << endl;
system ("PAUSE");
system ("CLS");

cout << "Inserire il paramentro di cancellazione ";
cin >> kappa;
cout << endl << endl;
Three->cancella (Three, kappa);

cout << "Di seguito e' riportata la configurazione dell'albero in seguito " << endl << endl
<< " alla valutazione del parametro: " << endl << endl << endl;
Three->visualizza2(Three);
cout << endl << endl;

system("PAUSE");
return 0;
}




il codice Ŕ corretto!!!!
il problema Ŕ come calcolo la profonditÓ dell'albero????

anx721
04-09-2004, 22:04
Se per profonditÓ intendi la lunghezza massima tra la radice e una delle foglie:



int albero::profonditÓ(albero *pNodo){
if(pNodo == NULL)
return 0;
int left = sx -> profonditÓ();
int right = dx -> profonditÓ();
if(left > right)
return left + 1;
else
return right + 1;
}

9178angel
04-09-2004, 22:29
nn funziona

9178angel
04-09-2004, 22:32
/* determina il massimo fra due interi */
int Massimo(int a, int b)
{
if (a > b)
return a;
else
return b;
} /* Massimo */

/*Calcola la profonditÓ dell'albero*/
int albero::deep(albero *pNodo)
{
int s, d,max;

if (pNodo == NULL)
return 0; /* l'albero vuoto ha profondita' 0 */
else {
/* calcola la profondita' dei sottoalberi */
s = deep(pNodo->sx);
d = deep(pNodo->dx);
/* l'albero complessivo ha profondita'
maggiore di uno */
return(Massimo(s, d) + 1);
}
};

io avevo provato cosý ma neanche qs funziona

anx721
04-09-2004, 22:44
Sý, c'era un errore.

Verisone static (calcola la profonditÓ di un albero passato come argomento); per calcolare la profonditÓ di un albero nodo va chiamata con la sintassi

int p = albero::profonditÓ(nodo);



class albero{
....
static int profonditÓ(pNodo *);
}


int albero::profonditÓ(albero *pNodo){
if(pNodo == NULL)
return 0;
int left = pNodo -> sx -> profonditÓ();
int right = pNodo -> dx -> profonditÓ();
if(left > right)
return left + 1;
else
return right + 1;
}



Versione non static; per calcolare la profonditÓ di un albero nodo va chiamata con la sintassi:

int p = nodo -> profonditÓ();



class albero{
....
int profonditÓ();
}


int albero::profonditÓ(){
int left = 0;
if(sx != NULL)
left = sx -> profonditÓ();
int right = 0;
if(dx != NULL)
right = dx -> profonditÓ();
if(left > right)
return left + 1;
else
return right + 1;
}


Nota: con queste funzioni se l'albero Ŕ composto dalla sola radice si ottiene 1, e cosi via.

9178angel
04-09-2004, 22:53
grazie in qs giorni sei stato un aiuto prezioso!!!notte!!! :)

Loading