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.

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

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)

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;


};

Alberi binari

Esempio

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

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.

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

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

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

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)