ΛΟΓ201: 2η Σειρά Ασκήσεων

Η παράδοση των ασκήσεων μπορεί να γίνει με έναν από τους ακόλουθους τρόπους κατά σειρά προτίμησης:

Με το ηλεκτρονικό ταχυδρομείο, στη διεύθυνση του διδάσκοντα (nickie@softlab.ntua.gr). Παρακαλώ, επισυνάψτε όλα τα αρχεία κώδικα (*.cpp, *.hpp, *.h) και μόνο αυτά σε ένα μόνο μήνυμα, γράψτε "LOG201, Exercise 2" στο θέμα (subject) του μηνύματος και μην ξεχάσετε να γράψετε μέσα στο μήνυμα το ονοματεπώνυμό σας.
Με δισκέττα στο διδάσκοντα, πριν ή μετά το μάθημα.

Άσκηση 1 (30%)

Να σχεδιασθεί και να υλοποιηθεί σε C++ ένα template κλάσης με όνομα BinaryTree<T>, που να υλοποιεί δένδρα δυαδικής αναζήτησης, τα στοιχεία των οποίων να έχουν τύπο T.

Nα υλοποιηθούν τουλάχιστον οι ακόλουθες μεθόδοι.

Default constructor, δημιουργία κενού δένδρου.
Destructor, καταστροφή δένδρου.
Προσθήκη στοιχείου με αντιγραφή του στο δένδρο:
void add (const T & e)
Εκτύπωση δένδρου (για λεπτομέρειες δείτε το αποτέλεσμα που περιέχεται στην άσκηση 3):
void print () const

Τα δένδρα δυαδικής αναζήτησης είναι δυαδικά δένδρα που πληρούν τις εξής βασικές συνθήκες, για κάθε κόμβο στο δένδρο με τιμή x:

Οι τιμές όλων των κόμβων που βρίσκονται στο αριστερό υποδένδρο είναι μικρότερες του x.
Παρόμοια, οι τιμές όλων των κόμβων του δεξιού υποδένδρου είναι μεγαλύτερες ή ίσες του x.

Η σύγκριση των τιμών γίνεται βάσει του operator < του τύπου T. Η προσθήκη ενός νέου στοιχείου σε ένα δένδρο γίνεται με την πρόσθεση ενός νέου φύλλου σε κατάλληλη θέση, έτσι ώστε να πληρούνται οι προαναφερθείσες συνθήκες.

Άσκηση 2 (60%)

Να σχεδιασθούν και να υλοποιηθούν σε C++ templates κλάσεων iterators, που θα υλοποιούν τους ακόλουθους τέσσερις διαφορετικούς τρόπους με τους οποίους μπορούμε να διατρέξουμε τα στοιχεία ενός δυαδικού δένδρου (για περισσότερες λεπτομέρειες δείτε το παράδειγμα στην άσκηση 3):

Κατά βάθος (depth first search), ενθεματικός (infix).
Κατά βάθος (depth first search), προθεματικός (prefix).
Κατά βάθος (depth first search), επιθεματικός (postfix).
Κατά πλάτος (breadth first search).

Για κάθε ένα τρόπο να υλοποιηθεί ένα template με τις ακόλουθες τουλάχιστον μεθόδους:

Μετακίνηση στο επόμενο στοιχείο του δένδρου (TRUE αν υπάρχει επόμενο, αλλιώς FALSE):
boolean get ()
Προσπέλαση του τρέχοντος στοιχείου του δένδρου:
const T & current () const

Τα template θα πρέπει να είναι πολυμορφικά και να κληρονομούν το βασικό αφηρημένο template κλάσης BinaryTreeIterator<T>, το οποίο θα περιέχει τις δηλώσεις των παραπάνω μεθόδων.

Σημείωση: διευκρινήσεις και υποδείξεις για αυτή την άσκηση καθώς και τμήματα χρήσιμου κώδικα θα δοθούν στις παραδόσεις και θα τοποθετηθούν στη σελίδα του μαθήματος.

Άσκηση 3 (10%)

Να ελεγχθεί η σωστή λειτουργία των templates που υλοποιήθηκαν στις προηγούμενες δυο ασκήσεις, με το ακόλουθο πρόγραμμα επίδειξης.

template <class T>
int iterate (const char * msg, BinaryTreeIterator<T> & i)
{
   cout << msg;
   while (i.get())
      cout << i.current() << " ";
   cout << "done\n";
}

int main ()
{
   int numbers [] = {42, 10, 7, 50, 55, 14, 12, 52, 30};

   BinaryTree<int> t;

   for (int i = 0; i < sizeof(numbers)/sizeof(int); i++)
      t.add(numbers[i]);

   cout << "Plain tree: ";
   t.print();
   cout << "\n";

   InfixIterator<int> i1(t);
   iterate("Infix: ", i1);

   PrefixIterator<int> i2(t);
   iterate("Prefix: ", i2);

   PostfixIterator<int> i3(t);
   iterate("Postfix: ", i3);

   BFSIterator<int> i4(t);
   iterate("BFS: ", i4);

   return 0;
}

Το αποτέλεσμα της εκτέλεσης του παραπάνω προγράμματος θα πρέπει να είναι το ακόλουθο:

Plain tree: 42 (10 (7 | 14 (12 | 30)) | 50 ( | 55 (52 | )))
Infix: 7 10 12 14 30 42 50 52 55 done
Prefix: 42 10 7 14 12 30 50 55 52 done
Postfix: 7 12 30 14 10 52 55 50 42 done
BFS: 42 10 50 7 14 55 12 30 52 done

Ημερομηνία παράδοσης (με δισκέττα):	Τρίτη 11 Απριλίου 2000
Ημερομηνία παράδοσης (με e-mail):	Παρασκευή 14 Απριλίου 2000
Ποσοστό επί της συνολικής βαθμολογίας:	10%