[c++]calcolo profondità

[9178angel]

 
#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]

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]

nn funziona

[9178angel]

/* 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]

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:rofondità(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]

grazie in qs giorni sei stato un aiuto prezioso!!!notte!!!