1

FONDAMENTI DI INFORMATICA IIIngegneria Gestionale

a.a. 2001-2002 - 4° Ciclo

Alberi

2

AlberiDefinizione

Un albero è una struttura dati non lineare perché i suoi nodi contengono due o più membri di link. Sono alberi binari quelli che contengono in ogni nodo esattamente due membri di link.

Elementi di un albero binario

Il nodo radice è il primo nodo di un albero, generalmente puntato da un puntatore esterno alla struttura dell’albero. I link del nodo radice, che convenzionalmente indicheremo come link di sinistra o link di destra, possono puntare a due altri nodi, detti nodi figli, o assumere il valore 0. Se esistono i nodi figli essi possono considerarsi come primi nodi rispettivamente del sottoalbero di sinistra e del sottoalbero di destra. I suddetti nodi figli possono a loro volta puntare ad altri nodi figli e ciascuno di essi può essere considerato il primo di un sottoalbero. Un nodo senza figli, ossia con entrambi i link a l valore 0, viene detto nodo foglia.

3

Alberi

Rappresentazione grafica di un albero

A

D

CB

Nodo radice

Nodo foglia

Puntatore esterno al nodo radice

Sottoalbero di destra

Nodo figlio

4

AlberiRappresentazione grafica semplificata di un albero

Nella rappresentazione grafica semplificata di un albero vengono presentati, senza particolari riquadrature, solo i dati contenuti nei nodi e, per mezzo di segmenti, i link tra i nodi. Un link mancante corrisponde nel nodo ad un puntatore di valore 0. Il nodo radice viene presentato in alto e, per convenzione i link sono diretti dall’alto verso il basso. L’esempio che segue è quello di un albero con un valore intero per nodo:

10

15 20

19171311

21

5

Alberi

Albero binario di ricerca

Un albero binario di ricerca è caratterizzato dal fatto che, dato un qualunque nodo, i valori dei dati contenuti nel sottoalbero di sinistra sono inferiori al valore del dato presente nel nodo in esame, che, a sua volta, è minore dei valori dei dati contenuti nel sottoalbero di destra.

Nota:

La forma di un albero di ricerca che corrisponde ad un insieme di dati non è unica: essa può variare secondo l’ordine in cui i valori sono inseriti nell’albero.

6

Alberi

Esempio di albero binario di ricerca

47

25 77

93654311

68177 4431

7

Alberi

Funzioni ricorsive

Si dicono funzioni ricorsive quelle funzioni che richiamano se stesse. Quando una funzione ricorsiva invoca se stessa la sua elaborazione s’interrompe a quel punto e il controllo viene ceduto ad una nuova istanza della funzione, che, a sua volta, può richiamare se stessa e quindi cedere il controllo ad una nuova istanza, …ecc. Se ad un certo punto un’ultima istanza della funzione riesce a completare i calcoli senza invocare se stessa essa può far ritornare il controllo all’istanza che l’ha invocata, la quale può completare i calcoli e restituire a sua volta il controllo alla precedente istanza e così via fino alla prima.

Una funzione ricorsiva deve avere quindi uno schema di operazioni del tipo descritto con lo schema a blocchi che segue.

8

Alberi

No

Funz_Ricors (parametro)

Parametro rela -tivo al caso base

Richiamo Funz_Ricors con

parametro tendente al caso

base

Elaborazioni

Si

Elaborazioni del caso base

return

9

AlberiEsempio di funzione ricorsiva

Funzione per il calcolo del fattoriale di un numero:int factorial (int number) {

if (number= =1)return 1;else

return number * factorial (number-1); }

Si può dare una rappresentazione grafica del funzionamento di una funzione ricorsiva indicando con una freccia il momento del suo richiamo ricorsivo, con un cerchietto, contenente il valore del parametro, la sua istanziazione e con un arco accompagnato dal valore del risultato il momento della restituzione del controllo. Nel caso della funzione factorial a cui sia stato passato il parametro number= 4, questa rappresentazione è:

3 2 14

12*13*24*6

10

Alberi// Classe TreeNode per la generazione dei nodi di un albero#ifndef TREENODE_H#define TREENODE_H

template< class NODETYPE > class Tree; // forward declaration

template< class NODETYPE > class TreeNode { friend class Tree< NODETYPE >;public: TreeNode( const NODETYPE &d ) : leftPtr( 0 ), data( d ), rightPtr( 0 ) { } NODETYPE getData() const { return data; }private: TreeNode< NODETYPE > *leftPtr; // pointer to left subtree TreeNode< NODETYPE > *rightPtr; // pointer to right subtree NODETYPE data;};#endif

11

Alberi

// Definition of template class Tree#ifndef TREE_H#define TREE_H#include <iostream>#include <cassert>#include "treenode.h"using std::endl;

template< class NODETYPE >class Tree {public: Tree( ); void insertNode( const NODETYPE & ); void preOrderTraversal( ) const; void inOrderTraversal( ) const; void postOrderTraversal( ) const;private: TreeNode< NODETYPE > *rootPtr;

12

Alberi

// utility functions void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & ); void preOrderHelper( TreeNode< NODETYPE > * ) const; void inOrderHelper( TreeNode< NODETYPE > * ) const; void postOrderHelper( TreeNode< NODETYPE > * ) const;};

template< class NODETYPE >Tree< NODETYPE >::Tree( ) { rootPtr = 0; }

template< class NODETYPE >void Tree< NODETYPE >::insertNode( const NODETYPE & value ) { insertNodeHelper( &rootPtr, value ); }

13

Alberi

// This function receives a pointer to a pointer so the// pointer can be modified.template< class NODETYPE >void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr, const NODETYPE &value ){ if ( *ptr == 0 ) { // tree (or sub tree) is empty *ptr = new TreeNode< NODETYPE > ( value ); assert( *ptr != 0 ); } else // tree is not empty if ( value < ( *ptr )->data ) insertNodeHelper( &( ( *ptr )->leftPtr ), value ); else if ( value > ( *ptr )->data ) insertNodeHelper( &( ( *ptr )->rightPtr ), value ); else cout << value << " dup" << endl;}

14

Alberi

template< class NODETYPE > void Tree< NODETYPE >::preOrderTraversal() const { preOrderHelper( rootPtr ); }

template< class NODETYPE >void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const{ if ( ptr != 0 ) { cout << ptr->data << ' '; preOrderHelper( ptr->leftPtr ); preOrderHelper( ptr->rightPtr ); }}

15

Alberi

template< class NODETYPE >void Tree< NODETYPE >::inOrderTraversal() const { inOrderHelper( rootPtr ); }

template< class NODETYPE >void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const{if ( ptr != 0 ) { inOrderHelper( ptr->leftPtr ); cout << ptr->data << ' '; inOrderHelper( ptr->rightPtr ); }}

16

Alberi

template< class NODETYPE >void Tree< NODETYPE >::postOrderTraversal() const { postOrderHelper( rootPtr ); }

template< class NODETYPE >void Tree< NODETYPE >::postOrderHelper( TreeNode< NODETYPE > *ptr ) const{ if ( ptr != 0 ) { postOrderHelper( ptr->leftPtr ); postOrderHelper( ptr->rightPtr ); cout << ptr->data << ' '; }}#endif

17

Alberi// Driver to test class Tree#include <iostream>#include <iomanip>#include "tree.h"using std::cout;using std::cin;using std::setiosflags;using std::ios;using std::setprecision;

int main(){ Tree< int > intTree; int intVal, i;

cout << "Enter 10 integer values:\n"; for( i = 0; i < 10; i++ ) { cin >> intVal; intTree.insertNode( intVal );}

18

Alberi cout << "\nPreorder traversal\n"; intTree.preOrderTraversal();

cout << "\nInorder traversal\n"; intTree.inOrderTraversal();

cout << "\nPostorder traversal\n"; intTree.postOrderTraversal();

Tree< double > doubleTree; double doubleVal;

cout << "\n\n\nEnter 10 double values:\n" << setiosflags( ios::fixed | ios::showpoint ) << setprecision( 1 ); for ( i = 0; i < 10; i++ ) { cin >> doubleVal; doubleTree.insertNode( doubleVal );}

19

Alberi

cout << "\nPreorder traversal\n"; doubleTree.preOrderTraversal();

cout << "\nInorder traversal\n"; doubleTree.inOrderTraversal();

cout << "\nPostorder traversal\n"; doubleTree.postOrderTraversal();

return 0;}

20

AlberiEnter 10 integer values:

50 25 75 12 33 67 88 6 13 68

Preorder traversal

50 25 12 6 13 33 75 67 68 88

Inorder traversal

6 12 13 25 33 50 67 68 75 88

Postorder traversal

6 13 12 33 25 68 67 88 75 50

Enter 10 double values:

39.2 16.5 82.7 3.3 65.2 90.8 1.1 4.4 89.5 92.5

Preorder traversal

39.2 16.5 3.3 1.1 4.4 82.7 65.2 90.8 89.5 92.5

Inorder traversal

1.1 3.3 4.4 16.5 39.2 65.2 82.7 89.5 90.8 92.5

Postorder traversal

1.1 4.4 3.3 16.5 65.2 89.5 92.5 90.8 82.7 39.2

21

Alberi

50

25 75

88673312

68136

Rappresentazione grafica dell’albero ottenuto con i 10 valori interi

22

Alberi

Visite ricorsive

Il grafico che segue rappresenta le visite ricorsive dei rami dell’albero effettuate con le funzioni preOrderTraversal, inOrderTraversal e postOrderTraversal. Ogni nodo è rappresentato con un cerchietto contenente il dato (intero) in esso immagazzinato. All’uscita da ciascun nodo la visita al ramo di sinistra è rappresentata da una freccia verticale, mentre la visita al ramo di destra da una freccia inclinata. Il ritorno dopo una visita è rappresentato con un arco. Nelle funzioni le visite ai rami di sinistra precedono sempre quelle dei rami di destra. Nelle tre funzioni le elaborazioni del dato del nodo sono eseguite come segue:

preOrder: prima della prima uscita dal nodo.

inOrder: prima della seconda uscita dal nodo.

postOrder: dopo il rientro definitivo nel nodo

23

Alberi

50

6

0 0

25

12

13

0 0

33

0 0

75

67

68

0 0

88

0 00

24

Alberi

Importanza degli alberi binari di ricerca

In un albero di ricerca ben bilanciato ogni livello conterrà un numero di elementi pari a circa il doppio degli elementi del livello precedente. Gli elementi di ogni livello crescono perciò con le potenze di 2 per cui al livello k gli elementi saranno 2k -1. Dato un albero con n elementi su k livelli essi saranno:

n= 20+ 21+ 22+ 23+... +2k -1= 2k-1

per cui approssimativamente il numero di livelli di un albero di ricerca ben bilanciato è pari a log2n. Ciò vuol dire che con 1000 elementi l’albero ha circa 10 livelli (infatti 210>1000), ossia una ricerca su 1000 elementi non richiede più di 10 confronti.