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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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