Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Salvatore Cuomo » 21.Esercizi su AlberiNick Parlante, BinaryTrees


Alberi

Visita di un albero.

PREORDINE (Preorder) o ordine anticipato: R – S – D

7 2 1 3 4 9.

POSTORDINE (Postorder) o ordine posticipato o polacco: S – D – R

2 1 7 4 9 3 5.

INORDINE (Inorder) o ordine simmetrico: S – R – D

2 7 1 5 4 3 9.

Ordinamento 1

Ordinamento 1


Struttura fondamentale di base

Definizione di un albero.

Un albero può essere implementato definendo una struttura di base nel seguente modo.

struct nodo {

// Albero di numeri interi

int DATO;

// Puntatore al sottoalbero destro

struct nodo *DX;

// Puntatore al sottoalbero sinistro

struct nodo *SX;

} NODO;

typedef struct nodo* tree

Ordinamento 2

Ordinamento 2


Struttura fondamentale di base

Funzioni su un albero.

Le principali funzione che si possono implementare per utilizzare un albero sono:

  • bool Is_Empty(tree ROOT)
  • tree Albero_Vuoto(void)
  • int Valore_Etichetta(tree ROOT)
  • tree Destro(tree ROOT)
  • tree Sinistro(tree ROOT)
  • tree Costruisci_Albero(int ETICHETTA,tree S,tree D)
Ordinamento 3

Ordinamento 3


Albero binario

Esempio

Il seguente programma sviluppa il codice necessario ad implementare un albero binario e le principali funzioni per operare con esso. Si riporta una implementazione in C++ mediante l’utilizzo delle classi.

La foglia di un albero viene definita mediante la struttura:

typedef struct nodo{

int valore;
nodo *sinistra;
nodo *destra;

};

Codice_C_1

Codice_C_1

Codice_C_2

Codice_C_2


Alberi binari

Esempio

Il programma principale è sviluppato in modo da testare tutti i metodi della classe BST vista in precedenza.

Codice_C_2

Codice_C_2

Codice_C_3

Codice_C_3


Alberi Binari

Esempio

La classe BST è composta di diversi memebri che di seguito verranno analizzati.

  • La funzione void bst :: clean(nodo* &carr) è il metodo deputato alla deallocazione dell’alabero.
  • La funzione bst :: bst() è il metodo per l’inizializzazione del bst.
  • La funzione bst :: ~bst() , metodo per la distruzione dell’albero.
Codice_C_4
Codice_C_5

Alberi Binari

Esempio

La classe BST è composta di diversi memebri che di seguito verranno analizzati.

  • La funzione void bst :: add(nodo* &carr, int valore), metodo per l’aggiunta di un elemento nel bst
  • La funzione nodo* bst :: binarySearch(nodo *carr, int valore), metodo per la ricerca di un elemento nel bst
Codice_C_6

Codice_C_6

Codice_C_7

Codice_C_7


Alberi Binari

Esempio

La classe BST è composta di diversi memebri che di seguito verranno analizzati.

  • La funzione void bst :: visualize_symmetricOrder(nodo* carr), metodo per la stampa in symmetric order del bst
  • La funzione void bst :: visualize_preOrder(nodo *carr), metodo per la stampa in pre order del bst
Codice_C_8

Codice_C_8

Codice_C_9

Codice_C_9


Alberi Binari

Esempio

La classe BST è composta di diversi memebri che di seguito verranno analizzati.

  • La funzione void bst :: visualize_postOrder(nodo *carr), Metodo per la stampa in post order del bst
  • La funzione unsigned int bst :: level(nodo* carr), metodo che restituisce il livello di profondità del bst
Codice_C_9

Codice_C_9

Codice_C_10

Codice_C_10


Alberi Binari

Esempio

La classe BST è composta di diversi memebri che di seguito verranno analizzati.

  • La funzione void bst :: bst2array(nodo* carr, int *arr, int &pos), metodo privato per salvare il bst in un array
  • La funzione void bst :: binaryInsertion(int *arr,int l, int r), metodo per l’inserimento di valori di un array in una lista.
  • La funzione void bst :: optimize(), metodo per l’ottimizzazione del bst (diminuisce il livello)
Codice_C_11
Codice_C_12

I materiali di supporto della lezione

Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition.Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3.

Esercizi

Nick Parlante, BinaryTrees

Nick Parlante, TreeListRecursion

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion