STRUTTURE NON LINEARI DINAMICHE


pagine di Roberto Ricci L.S. "A. Righi", Bologna. Ultima revisione


 
 

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:

con parentesi annidate:
  • preordine: 1(2(4(()7)5)3(6()))
  • in ordine: (((4(7))2(5))1((6)3))
  • postordine: (((()7)45)2(6())3)1
con un simbolo per rappresentare l'abero vuoto (una foglia è seguita da due alberi vuoti):
  • preordine: 124*7**5**36***
  • in ordine: *4*7*2*5*1*6*3* ( non è univoca)
  • postordine: ***74**52**6*31
Una implementazione in C basata su puntatori e sull'allocazione dinamica della memoria è il seguente:

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

typedef	nodo *albBin;
o anche meglio

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


  La seguente è la descrizione di un algoritmo di ricerca binaria:
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
Tale algoritmo è applicabile solo a liste ordinate (la cui manutenzione, cioè l'inserirmento o la cancellazione degli elementi, ha quindi un costo) ma ha un'efficienza decisamente maggiore rispetto a una ricerca di tipo sequenziale.

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

Un ABR, i cui valori si dicono anche chiavi, è tale che:
  • nel sottoalbero sinistro le chiavi sono strettamente minori della chiave della radice,
  • nel sottoalbero destro le chiavi sono strettamente maggiori della chiave della radice.
Si noti che in un ABR non ci possono essere nodi diversi con la stessa chiave.
  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 è:

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);
    	 }
    }
    

pagine di Roberto Ricci L.S. "A. Righi", Bologna. Ultima revisione