Programmi C/C++ - prof.Claudio Maccherani

Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
A.B.R. (Albero Binario di Ricerca)

 /* Adt, dato astratto ABR, Albero Binario di Ricerca
    Dev-C++ - prof. Claudio Maccherani - Perugia - 2008/09 */
    (parziale rielaborazione di un programma di Alessio Luffarelli)

 #include <stdio.h>     
 #include <iostream.h>                             
 #include <windows.h> 
 #include <stdlib.h>
 #include <time.h>

 using namespace std;

 struct nodo {
   int DATO;        //albero di valori interi
   struct nodo *DX; //puntatore al sottoalbero destro
   struct nodo *SX; //puntatore al sottoalbero sinistro
   }NODO;

 typedef struct nodo* albero; // dichiarazione del nuovo tipo di dato: albero
 albero t1;                   // dichiarazione di t1 di tipo 'albero'
 const int N=7;               // numero di nodi dell'albero
 int col=10;                  // colonna per display vari

 int gotoxy(int r, int c) { // posiziona il cusore a riga 'r' e colonna 'c' 
   HANDLE Hout; CONSOLE_SCREEN_BUFFER_INFO ConsoleInfo; 
   Hout = GetStdHandle(STD_OUTPUT_HANDLE); 
   ConsoleInfo.dwCursorPosition.Y = r; ConsoleInfo.dwCursorPosition.X = c;     
   SetConsoleCursorPosition(Hout,ConsoleInfo.dwCursorPosition); }

 bool Is_Empty(albero RADICE) //da TRUE se albero è vuoto, altrimenti FALSE
 { return(RADICE==NULL); }    //NB: questo è un confronto, non un'assegnazione

 albero Albero_Vuoto(void)    //costruisce un albero vuoto
 { return(NULL); }

 int Valore_Etichetta(albero RADICE) //da il valore (o etichetta) del nodo
 { if (Is_Empty(RADICE)) abort();
   else return(RADICE->DATO); }

 albero Sinistro(albero RADICE)      //da il puntatore al sottoalbero sinistro
 { if (Is_Empty(RADICE)) return(NULL);
   else return(RADICE->SX); }

 albero Destro(albero RADICE)        //da il puntatore al sottoalbero destro
 { if (Is_Empty(RADICE)) return(NULL);
   else return(RADICE->DX); }

 albero Costruisci_Albero(int ETICHETTA,albero S,albero D)//costrisce un albero
 {	albero RADICE;                                        //binario non ordinato
	RADICE = (nodo *) malloc(sizeof(NODO)); //chiede l'indirizzo di una nuova
	RADICE->DATO = ETICHETTA;               // cella di memoria
	RADICE->SX = S;
	RADICE->DX = D;
	return (RADICE);   }

 void Preorder(albero RADICE)  // visita in ordine anticipato o preorder
 {	if (!(Is_Empty(RADICE))) {
		cout<<Valore_Etichetta(RADICE)<<"  ";
		Preorder(Sinistro(RADICE));
		Preorder(Destro(RADICE)); }   }

 void Inorder(albero RADICE)   // visita in ordine simmetrico o inorder
 {	if (!(Is_Empty(RADICE))) {
		Inorder(Sinistro(RADICE));
		cout<<Valore_Etichetta(RADICE)<<"  ";
		Inorder(Destro(RADICE)); }    }

 void Postorder(albero RADICE) // visita in ordine posticipato o postorder
 {	if (!(Is_Empty(RADICE))) {
		Postorder(Sinistro(RADICE));
		Postorder(Destro(RADICE));
		cout<<Valore_Etichetta(RADICE)<<"  "; }   }

 int ContaNodi(albero RADICE)  //restituisce il numero dei nodi dell'albero
 {	if(Is_Empty(RADICE)) return(0);
	else return(1 + ContaNodi(Sinistro(RADICE)) + ContaNodi(Destro(RADICE)));  }

 int ContaFoglie(albero RADICE)//restituisce il numero delle foglie dell'albero
 { 	if(Is_Empty(RADICE)) 
		return(0);
    else {
	   if ((Sinistro(RADICE)==NULL) && (Destro(RADICE)==NULL))
		   return(1);
	   else return(ContaFoglie(Sinistro(RADICE))+ContaFoglie(Destro(RADICE)));
    }  }

 bool Perf_Bil(albero RADICE) // da TRUE se l'albero è perfettamente bilanciato
 {	if (Is_Empty(RADICE)) return(true);	//Oppure ERROR
	else {
        //se il nodo è una foglia..
        if ((Sinistro(RADICE)==NULL)&&(Destro(RADICE)==NULL))
           return(true);
        else {
            //se il nodo ha tutti e due i figli..
            if ((Sinistro(RADICE)!=NULL) && (Destro(RADICE)!=NULL))
                return( Perf_Bil(Sinistro(RADICE)) && Perf_Bil(Destro(RADICE)));
            else return(false);
		}
	}
 }

 bool Ricerca(albero RADICE,int X) //cerca X nel sottoalbero di RADICE
 { 	if (Is_Empty(RADICE))
		return(false);
	else {
		if (X==Valore_Etichetta(RADICE))
			return(true);
		else
			return(Ricerca(Sinistro(RADICE),X)||Ricerca(Destro(RADICE),X)); } }

 int Altezza(albero N)	//da l'altezza di un nodo (distanza dalla radice)
 {   int ALTD=0,ALTS=0;
	if (Is_Empty(N)) return(-1);
	else {
		ALTS=Altezza(Sinistro(N));
		ALTD=Altezza(Destro(N));
		if (ALTS>ALTD) return(ALTS+1);
		else return(ALTD+1);  } }

 albero Ins_Ord(int E,albero RADICE) //Costruisce un albero binario di ricerca
 {	if (Is_Empty(RADICE)) {          //(un albero "ordinato", ma NON bilanciato)
		RADICE=(albero)malloc(sizeof(NODO)); //chiede una cella di memoria
		RADICE->DATO=E;
		RADICE->SX=NULL;
		RADICE->DX=NULL;
		return RADICE;
	}
	else {
		if(E<Valore_Etichetta(RADICE)) {
			RADICE->SX=Ins_Ord(E,Sinistro(RADICE));
			return RADICE;
		}
		else {
			RADICE->DX=Ins_Ord(E,Destro(RADICE));
			return RADICE;
		}
	}
 }

 bool RicercaBinaria(int X,albero RADICE) //Ricerca dicotomica (binaria) su ABR
 {	if (Is_Empty(RADICE)) return(false);
	else {
		if (X==Valore_Etichetta(RADICE)) return(true);
		else {
			if (X < Valore_Etichetta(RADICE))
				return( RicercaBinaria(X,Sinistro(RADICE)) );
			else 
				return( RicercaBinaria(X,Destro(RADICE)) );
		}
	}
 }

 int creazione(int flag) { // creazione di un A.B.R. di 7 nodi (3 livelli) ----
   int x; srand(time(0));
   system("cls"); gotoxy(1,col); printf("Creazione di un Albero Ordinato ");
   if (flag == 0) printf("(casuale, non ABR)");
      else        printf("(casuale, non ABR, 1 solo ramo)");
   t1 = Albero_Vuoto(); // crea l'albero vuoto
   for (int i=1; i<=N;i++) {
      if (flag == 0) { x = rand() %1000; t1 = Ins_Ord(x,t1); }
         else t1 = Ins_Ord(i*10,t1);   }
   gotoxy(3,col);
   printf("Creato un albero di %d nodi (casuali) ordinato NON bilanciato ",N);   
   getchar(); return 0; }

 int informazioni() {
   system("cls"); gotoxy(1,col); printf("Informazioni generali sull'A.B.R. "); 
   gotoxy(3,col); cout << "Radice:         " << Valore_Etichetta(t1);
   gotoxy(4,col); cout << "Numero Nodi:    " << ContaNodi(t1);
   gotoxy(5,col); cout << "Numero Foglie:  " << ContaFoglie(t1);
   gotoxy(6,col); cout << "Altezza Albero: " << Altezza(t1)
                       << " (" << Altezza(t1)+1 << " livelli)";
   gotoxy(7,col); 
   if (Perf_Bil(t1)) cout << "Albero BILANCIATO ";
	  else cout << "Albero NON bilanciato ";
   gotoxy(7,col+25); 
   getchar(); return 0; }

 int visite() { // visite dell'albero: anticipata, simmetrica e posticipata ---
   system("cls"); gotoxy(1,col); printf("Visite sull'A.B.R. "); 
   gotoxy(3,0); printf("Ordine Anticipato:  ");
   if (N!=7) { printf("\n"); } Preorder(t1);
   gotoxy(5,0); printf("Ordine Simmetrico:  ");
   if (N!=7) { printf("\n"); } Inorder(t1);
   gotoxy(7,0); printf("Ordine Posticipato: ");
   if (N!=7) { printf("\n"); } Postorder(t1);
   getchar(); return 0; }

 int ricerca() { // ricerca di un elemento nell'A.B.R. ------------------------
   int x;
   system("cls"); gotoxy(1,col); printf("Ricerca nell'A.B.R. "); 
   gotoxy(3,col); printf("Radice   dell'A.B.R.:  "); Valore_Etichetta(t1);
   gotoxy(4,col); printf("Elementi dell'A.B.R.:  "); Inorder(t1);
   gotoxy(6,col); printf("Elemento da cercare :  "); cin >> x;
   gotoxy(6,col+30);
   if (RicercaBinaria(x,t1)) cout << "Valore TROVATO ";
      else cout << "Valore NON trovato ";
   getchar(); return 0; }
   
 int inserimento() { // inserimento di un valore nell'albero
   system("cls"); gotoxy(1,col); printf("Inserimento di un nodo sull'A.B.R. "); 
   getchar(); return 0;}   

 void CreaArray(nodo* radice,int array[],int &i) {       //per il bilanciamento
	if(radice->SX!=NULL)
		CreaArray(radice->SX,array,i);
	array[i]=radice->DATO;
	i++;
	if(radice->DX!=NULL)
		CreaArray(radice->DX,array,i); }

 void DistruggiAlbero(nodo* &radice) {                   //per il bilanciamento
	if(radice!=NULL) {
		if(radice->SX!=NULL)
			DistruggiAlbero(radice->SX);
		if(radice->DX!=NULL)
			DistruggiAlbero(radice->DX);
		delete radice;
		radice=NULL; } }

 nodo* RicavaAlbero(int primo, int ultimo, int array[]) {//per il bilanciamento
	int mediana;
	if(ultimo>=primo) {
		mediana=(primo+ultimo)/2;
		nodo* tmp=new nodo;
		tmp->DATO=array[mediana];
		tmp->SX=RicavaAlbero(primo,mediana-1,array);
		tmp->DX=RicavaAlbero(mediana+1,ultimo,array);
		return tmp; }
	return NULL; }

 void bilanciamento(nodo* &radice) { // bilanciamento dell'albero ordinato ----
	int array[N];                    // che così diviene A.B.R. !
	int i=1;
    system("cls"); gotoxy(1,col);
    printf("Bilanciamento Albero Binario Ordinato "); 
	CreaArray(radice,array,i);
    printf("\n\n\n"); for (i=1;i<=N;i++) cout<<i<<" - "<<array[i]<<"\n";
	DistruggiAlbero(radice);
	int p=1;
	int u=N;
	radice=RicavaAlbero(p,u,array);
    gotoxy(3,col); printf("L'Albero e' divenuto A.B.R. ! "); getchar(); }

 int main() { // programma principale -----------------------------------------
   int scelta;             
   do {
      system("cls"); scelta = -1;
      gotoxy( 1,col); printf("Adt - Albero Binario di Ricerca <ClaMa>"); 
      gotoxy( 4,col); printf("1 - Creazione (ordinato, casuale, non ABR) "); 
      gotoxy( 6,col);
      printf("2 - Creazione (ordinato, casuale, non ABR, 1 solo ramo) "); 
      gotoxy( 8,col); printf("3 - Bilanciamento (diviene ABR) "); 
      gotoxy(10,col); printf("4 - Informazioni"); 
      gotoxy(12,col); printf("5 - Visite      "); 
      gotoxy(14,col); printf("6 - Ricerca     "); 
      gotoxy(16,col); printf("7 - Inserimento "); 
      gotoxy(18,col); printf("    scegli (0=fine) ");
      cin>>scelta; 
      switch (scelta) {
           case 1: { creazione(0);      break; } 
           case 2: { creazione(1);      break; } 
           case 3: { bilanciamento(t1); break; } 
           case 4: { informazioni();    break; }
           case 5: { visite();          break; }
           case 6: { ricerca();         break; }           
           case 7: { inserimento();     break; } }
      }     
   while (scelta!= 0);
   return 0; }