ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Τμήμα Ηλεκτρονικών Μηχ. και Μηχ. Υπολογιστών ΛΟΓ 201: Τεχνολογία Λογισμικού ΙΙ http://www.softlab.ntua.gr/~nickie/TUC/log201/

2η Σειρά Ασκήσεων
Υποδείξεις

Άσκηση 1

Μια σύντομη περιγραφή των δένδρων δυαδικής αναζήτησης δίνεται στην εκφώνηση της άσκησης. Εκτενέστερες περιγραφές μπορείτε να βρείτε σε βιβλία δομών δεδομένων.

Η σύγκριση των τιμών γίνεται με τον τελεστή < ο οποίος υποθέτουμε ότι υποστηρίζεται από τον τύπο T.

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

• Αν το δένδρο είναι κενό, η προσθήκη είναι τετριμμένη.
• Αν η τιμή που πρέπει να προστεθεί είναι μικρότερη από την τιμή της ρίζας του δένδρου, τότε η προσθήκη πρέπει να γίνει στο αριστερό παιδί.
• Διαφορετικά, στο δεξί παιδί.

Οι τιμές αντιγράφονται στα δένδρα, επομένως υποθέτουμε επίσης ότι ο τύπος T διαθέτει copy constructor. Η άσκηση δε ζητάει να γίνεται κανενός είδους "ζύγισμα" των δένδρων.

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

• Αν το δένδρο είναι κενό δεν εκτυπώνεται τίποτα.
• Αν το δένδρο δεν έχει παιδιά εκτυπώνεται μόνο η τιμή της ρίζας.
• Διαφορετικά, εκτυπώνεται η τιμή της ρίζας και στη συνέχεια (μέσα σε παρενθέσεις) πρώτα το αριστερό παιδί και μετά (χωρισμένο με κάθετο) το δεξί παιδί.

Άσκηση 2

Οι iterators που ζητείται να υλοποιηθούν ανήκουν σε δυο μεγάλες κατηγορίες:

• Κατά βάθος (depth first search), όπου εξετάζεται πρώτα ολόκληρο το αριστερό παιδί ενός κόμβου, προτού προχωρήσουμε στο δεξί παιδί.
• Κατά πλάτος (breadth first search), όπου εξετάζονται πρώτα όλοι οι κόμβοι που ανήκουν στο ίδιο επίπεδο του δένδρου, προτού προχωρήσουμε σε χαμηλότερο επίπεδο.

Στην πρώτη κατηγορία, διακρίνουμε τρεις τρόπους διάσχισης:

• Ενθεματικός (infix), όπου εξετάζεται πρώτα το αριστερό παιδί, μετά η ρίζα και μετά το δεξί.
• Προθεματικός (prefix), όπου εξετάζεται πρώτα η ρίζα, μετά το αριστερό παιδί και μετά το δεξί.
• Επιθεματικός (postfix), όπου εξετάζεται πρώτα το αριστερό παιδί, μετά το δεξί και στο τέλος η ρίζα.

Το παράδειγμα στο τέλος της εκφώνησης της άσκησης 3 περιγράφει όλους τους ζητούμενους τρόπους διάσχισης. Η υλοποίησή τους είναι εύκολο να γίνει αναδρομικά.

Ένας απλός τρόπος υλοποίησης των iterators είναι ο ακόλουθος. Μπορείτε να ενσωματώσετε μια ουρά κόμβων σε κάθε iterator, την οποία θα γεμίζετε στον constructor χρησιμοποιώντας την αναδρομική υλοποίηση των τρόπων διάσχισης. Στη συνέχεια, οι μέθοδοι get και current θα βλέπουν μόνο την ουρά και θα επιστρέφουν στοιχεία από αυτήν.

Για τη διευκόλυνσή σας, μπορείτε να χρησιμοποιήσετε στη λύση της άσκησης τα ακόλουθα templates:

• Template Queue<T>: υλοποίηση ουράς, αρχείο queue.hpp
• Template Stack<T>: υλοποίηση στοίβας, αρχείο stack.hpp
• Λογικές τιμές: υλοποίηση, αρχείο boolean.hpp

Η χρήση των παραπάνω δεν είναι υποχρεωτική, επίσης δεν είναι απαραίτητο να χρησιμοποιήσετε και τα δύο.

Τα templates των iterators θα πρέπει να κληρονομούν το βασικό αφηρημένο template BinaryTreeIterator<T>. Αυτό σημαίνει ότι θα έχετε:

template <class T>
   class InfixIterator : public BinaryTreeIterator<T>
   ...
template <class T>
   class PrefixIterator : public BinaryTreeIterator<T>
   ...
template <class T>
   class PostfixIterator : public BinaryTreeIterator<T>
   ...
template <class T>
   class BFSIterator : public BinaryTreeIterator<T>
   ...

Άσκηση 3

Ο κώδικας που δίνεται θα πρέπει να μπορεί να ενσωματωθεί στο πρόγραμμά σας όπως ακριβώς είναι και να εκτυπώνει τα αποτελέσματα που δίνονται στην εκφώνηση.