Il progetto consiste nella realizzazione di una classe generica che implementa
un albero binario di ricerca. L'albero è formato da un insieme di elementi T
contenuti in nodi connessi in una struttura gerarchica padre-figlio e NON deve
permettere l'inserimento di dati duplicati. Deve essere possibile per l'utente
scegliere la strategia usata per confrontare due dati T
.
Oltre ai metodi fondamentali, la classe deve permettere:
- Di conoscere il numero totale di dati inseriti nell'albero.
- Il controllo di esistenza di un elemento
T
. - Di accedere ai dati presenti nell'albero tramite un iteratore a sola lettura e di tipo forward. L'ordine con il quale sono ritornati i dati non è rilevante.
- Di stampare il contenuto dell'albero (anche usando
operator<<
). - Implementare inoltre un metodo
subtree
che, passato un datod
dello stesso tipo del dato contenuto nell'albero, ritorna un nuovo albero. Il nuovo albero deve corrispondere al sottoalbero avente come radice il nodo con il valored
. Ad esempio l'esecuzione diB=A.subtree(8)
potrebbe corrispondere alla situazione in figura: - Implementare una funzione globale
printIF
che dato un albero binario di tipoT
, e un predicatoP
, stampa a schermo tutti i valori contenuti nell'albero che soddisfano il predicato.
Utilizzare dove opportuno la gestione delle eccezioni. Gestite con una logica opportuna i casi limite/di errore.
- Se non indicato diversamente, nella progettazione della classe, è
vietato l'uso di librerie esterne e strutture dati container della std library come
std::vector
,std::list
e simili. È consentito il loro uso nel codice di test nel main. - A parte
nullptr
, non potete utilizzare altri costrutti C++11 e oltre. - Nella classe, è consentito l'uso della gerarchia di eccezioni standard,
delle asserzioni, la gerarchia degli stream e la funzione
std::swap
. - Per sicurezza, tutti i metodi dell'interfaccia pubblica devono essere esplicitamente testati nel main anche su tipi custom.
- Usare Valgrind per testare problemi di memoria.
- Evitate di usare "test" come nome dell'eseguibile. Potrebbe dare dei problemi sotto msys.