Programmazione I - Esercitazione

Istruzioni

Lo studente leggerà attentamente il testo e produrrà esattamente ciò che gli viene richesto...

Testo della prova

Scrivere una funzione binaryTreeSearch che sia in grado di identificare un valore specifico in un albero binario (un albero nel quale ogni nodo, se ha figli, ne ha due). La funzione dovrebbe prendere come argomento un puntatore al nodo radice dell'albero binario ed eseguire la ricerca della chiave. Se il nodo, contenente la chiave che si cerca, viene trovato allora la funzione deve restituire il puntatore a quel nodo altrimenti la funzione dovrebbe restituire il puntatore a NULL.

In particolare

1. Si definisca un template di classe Tree che possegga un costruttore e le funzioni di visita relative all'albero preOrderTraversal() const; inOrderTraversal() const; postOrderTraversal() const e una funzione di inserimento dei nodi insertNode( const NODETYPE & ); si adoperi un template di classe per la classe Nodetype affinché l'albero sia di un tipo generico T.
2. Si gestisca la allocazione dinamica della classe Tree e a tal proposito, lo studente costruisca una classe errore che gestisca le eccezioni di errori più comuni nella manipolazione dell'albero (indirizzo di memoria non disponibile, albero vuoto, albero che supera la dimensione massima, immissione errata, etc).
3. Lo studente provi con opportuni casi di prova (non solo quello mostrato negli esempi d'uso) l'effettivo funzionamento del suo progetto.

Esempi d'uso

The values being placed in the tree are:

96 96 58 31 44 0 12 61 99 32 29 79 55 1

Enter a value to search for: 1

Comparing 1 to 96; smaller, walk left

Comparing 1 to 58; smaller, walk left

Comparing 1 to 31; smaller, walk left

Comparing 1 to 12; smaller, walk left

Comparing 1 to 0; larger, walk right

Comparing 1 to 1; search complete

I was found