STRUTTURE NON LINEARI DINAMICHE

• INDICE
• 1. Alberi binari
  2. Alberi binari di ricerca
  3. Alberi generali
• Soluzioni proposte

Alberi binari

Definito in modo ricorsivo, un albero binario è:

vuoto un elemento (radice) seguito da due aberi.

Ad esempio in figura è rappresentato un albero con radice 1 e sottoalbero sinistro che contiene i valori 2, 4, 5, 7.
Una tale struttura dati è rappresentabile bidimensionalmente sfruttando ad esempio righe e colonne della pagina:

a grafo, come in precedenza: 3 6 1 5 2 7 4

con indentazione: 1 2 4 - 7 5 3 6

Si possono dare anche rappresentazioni unidimensionali basate su modi diversi di visitare l'albero:

• preordine (o anticipata o prefissa): considera il valore del nodo corrente, visita sottoalbero sinistro, visita sottoalbero destro.
• in ordine (o simmetrica o infissa): visita sottoalbero sinistro, considera il valore del nodo corrente, visita sottoalbero destro.
• postordine (o posticipata o postfissa): visita sottoalbero sinistro, visita sottoalbero destro, considera il valore del nodo corrente,

typedef struct elemento {
	 	struct elemento *sin;
	 	tipoValore value;
	 	struct elemento *des;
} nodo;

typedef	nodo *albBin;

typedef	struct nodo *albBin;

struct nodo {
	 	albBin sin;
	 	tipoValore value;
	 	albBin des;
};

1. Per maggiore dimestichezza con la struttura ad albero binario eseguire il programma albBin1.cpp per la lettura di un albero binario di interi e la sua visualizzazione sia in forma di grafo sia in preordine in forma unidimensionale
2. Analizzare il programma precedente e aggiungere procedure per la visualizzazione dell’albero in ordine e postordine
3. Realizzare una function che dato un albero binario visualizzi le sue foglie, cioè i valori ai nodi privi di sottoalberi
4. Realizzare un programma per leggere una stringa formata di simboli di operazione algebrica '+', '*', '-', '/' e lettere - ad es. +*abc, cioè una espressione algebrica in forma prefissa - per trasformarla in un albero avente come foglie le lettere e visualizzarla in forma infissa e postfissa

   Come eventuale approfondimento

5. Modificare il programma albBin1.cpp in modo che il tipo di valori dell'albero siano stringhe e il carattere '*'indichi che il sottoalbero è vuoto.
6. Realizzare un programma per leggere un albero di caratteri dato in forma unidimensionale in preordine con carattere '*' per sottoalbero vuoto facendo uso della function seguente:

   albBin leggePreOrd(stringa &s){
     albBin p = NULL;
     if (*s != '*') {
   	 p=(albBin) malloc(sizeof(nodo));
   	 p->value=*s;
   	 p->sin=leggePreOrd(++s);
   	 p->des=leggePreOrd(++s);
     }
     return p;
   }
   

7. Aggiungere al programma precedente una function per la lettura di un albero binario di caratteri dato come stringa in postordine con carattere '*' per sottoalbero vuoto (suggerimento: realizzare una function iterativa anziché ricorsiva e usare una pila per i sottoalberi sinistro e destro)
8. Realizzare un programma per leggere un albero di caratteri dato in forma unidimensionale in preordine con parentesi basato ad esempi su una function come la seguente:

   albBin leggeInOrd(stringa &s){
     albBin p = NULL;
     if (*s != '\0'){
             if (*s == '('){
                     p=(albBin) malloc(sizeof(nodoA));
   		          p->sin=leggeInOrd(++s);
   		          p->value=*s;
   		          p->des=leggeInOrd(++s);
             }else
                     while (*s == ')')
                         s++; 
     }
     return p;
   }
   

   e aggiungere function per la lettura in ordine e in postordine
9. Realizzare un programma per leggere una stringa formata di simboli di operazione algebrica '+', '*', '-', '/' e lettere - ad es. a*b+c, cioè una espressione algebrica - per trasformarla in un albero avente come foglie le lettere e visualizzarla in forma prefissa e infissa

Alberi binari di ricerca

ripeti
	confronta il dato con uno a metà della sequenza
	se il dato è minore 
		cerca nella prima metà
	altrimenti 
		cerca nella seconda metà
fintantoché l'hai trovato e ci sono elementi tra i quali cercare ancora

Un albero binario di ricerca (ABR o anche BST) è una struttura dati più efficace di una sequenza ordinata per implementare algoritmi di ricerca binaria.

nel sottoalbero sinistro le chiavi sono strettamente minori della chiave della radice, nel sottoalbero destro le chiavi sono strettamente maggiori della chiave della radice.

1. Aggiungere nel programma albBin1.cpp una procedura in grado di visualizzare se l'albero binario che viene letto è di ricerca crescente. (Come passaggio intermedio costruire la lista delle chiavi che si ottiene visitando l'albero in ordine, che nel caso di un ABR deve risultare ordinato)
2. Realizzare un programma per la lettura di n numeri interi da inserire in un albero binario di ricerca

   se l'albero non è vuoto
   	se il valore di x è uguale a quello della radice 
   		l'elemento non va inserito perché già presente 
   	se il valore di x è minore di quello della radice  
   		se il sottoalbero sinistro è vuoto 
   			inseriamo x nel sottoalbero sinistro 
   	se il valore di x è maggiore di quello della radice 
   			inseriamo x nel sottoalbero destro
   altrimenti
   	creiamo un nodo con i due sottoalberi vuoti
   	inseriamo x come chiave
   

   Aggiungere anche procedure per la visualizzazione in preordine, in ordine e postordine. Notare che la visita in ordine simmetrico di un ABR genera una sequenza crescente di tutte le sue chiavi.
3. Aggiungere al programma precedente una function per la ricerca di un elemento in un albero binario di ricerca. Ad esempio seguire un algoritmo come il seguente:

   Se l'albero è vuoto 
   	la ricerca termina subito con fallimento. 
   altrimenti
   	si confronta il valore cercato con quello contenuto nella radice dell'albero: 
   		Se i due valori coincidono 
   			la ricerca termina con successo  
   		Se il valore cercato è minore di quello contenuto nella radice 
   			la ricerca prosegue ricorsivamente nel sottoalbero sinistro. 
   		Se è invece maggiore 
   			la ricerca prosegue nel sottoalbero destro.  
   

   Nella peggiore della ipotesi la ricerca ha una durata proporzionale alla massima profondità dell'albero.

Alberi generali

Definito in modo ricorsivo, un albero è:

• vuoto
• un elemento (radice) associato a una foresta di (sotto)alberi, cioè una lista di sottoalberi.

Ad esempio:

In C si può definire un albero generale nel modo seguente: typedef int tipoValore; typedef struct nodoA *albero; typedef struct nodoF *foresta; struct nodoA{ tipoValore value; foresta next; }; struct nodoF{ albero value; foresta next; };

1. Completare il seguente programma inserendo le opportune definizioni delle strutture dei dati, con una function per creare un albero di data radice e con data foresta, una function per estrarre la foresta dei sottoalberi, una function per estrarre la radice.

   albero creaAlbero(tipoValore, foresta);
   foresta sottoAlberi(albero);
   tipoValore radAlbero(albero);
   
   albero legge(int);
   void visGraf(int, albero);
   
   
   main(){
   	 albero p;
   	 printf("Inserisci numeri interi, '0' per terminare il ramo:\n");
   	 p = legge(0);
   	 printf("\nUna visualizzazione come grafo:\n");
   	 visGraf(0,p);
   }
   
   albero legge(int n){
   	tipoValore elem;
   	albero p=NULL;
   	printf("\n");
   	int i;
   	for (i=0;i<n;i++)
   			printf("  ");
   	printf("? ");
   	scanf("%d",&elem);
   	foresta f=NULL;
   	if (elem!=0){
   		foresta fAus=(foresta) malloc(sizeof(nodoF));
   		fAus->value=legge(n+1);
   		while (fAus->value!=NULL){
   			fAus->next=f;
   			f=fAus;
   			fAus= (foresta) malloc(sizeof(nodoF));
   			fAus->value=legge(n+1);
   		}
   		p=creaAlbero(elem,f);
   	}
   	return p;
   }
   
   void visGraf(int n, albero p){
   	 if (p!=NULL){
   		int i;
   		for (i=0;i<n;i++)
   				printf("   ");
   		printf("%d",p->value);
   		printf("\n");
   		foresta f= sottoAlberi(p);
   		while (f!=NULL){
   				visGraf(n+1,f->value);
   				f=f->next;
   		}
   	 }
   }
   
   

2. aggiungere al programma precedente una function per visualizzare solo le foglie dell'albero
3. Qualunque albero può esser sempre rappresentato da un albero binario. Ecco una rappresentazione dell'albero iniziale mediante un albero binario:
   
   Completare il seguente programma per realizzare tale possibilità.

   
   albBin legge(int);
   void visGraf(int, albBin);
   void visGrafBin(int, albBin);
   
   main(){
   	printf("Inserisci numeri interi, '0' per terminare il ramo:\n");
   	albBin p=legge(0);
   	printf("\nUna visualizzazione come grafo:\n");
   	visGraf(0,p);
   	printf("\nUna visualizzazione come albero binario:\n");
   	visGrafBin(0,p);
   }
   
   
   
   albBin legge(int n){
   	tipoValore elem;
   	albBin p=NULL;
   	printf("\n");
   	int i;
   	for (i=0;i<n;i++)
   			printf("  ");
   	printf("? ");
   	scanf("%d",&elem);
   	if (elem!=0){
   		p=(albBin) malloc(sizeof(nodo));
   		p->value= elem;
   		p->sin=legge(n+1);
   		p->des=legge(n);
   	}
   	return p;
   }
   
   void visGraf(int n, albBin p){
   	 if (p!=NULL){
   		int i;
   		for (i=0;i<n;i++)
   				printf("   ");
   		printf("%d",p->value);
   		printf("\n");
   		visGraf(n+1,p->sin);
   		visGraf(n,p->des);
   	 }
   }