Οδηγίες
Άλλαξε τη ρίζα ενός δέντρου σε έναν επιλεγμένο κόμβο.
Ένα δέντρο είναι ένας ειδικός τύπος γράφου, όπου όλοι οι κόμβοι είναι συνδεδεμένοι αλλά δεν υπάρχουν κύκλοι.
Αυτό σημαίνει ότι υπάρχει ακριβώς ένα μονοπάτι για να πας από έναν κόμβο σε έναν άλλο, για οποιοδήποτε ζεύγος κόμβων.
Αυτή η άσκηση έχει να κάνει με τον επαναπροσανατολισμό ενός δέντρου, ώστε να δεις τα πράγματα από μια διαφορετική οπτική γωνία.
Για παράδειγμα, τα οικογενειακά δέντρα παρουσιάζονται συνήθως από την οπτική του προγόνου:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Όμως ένα δέντρο δεν έχει κάποια εγγενή κατεύθυνση.
Οι ίδιες πληροφορίες μπορούν να παρουσιαστούν από την οπτική γωνία οποιουδήποτε άλλου κόμβου του δέντρου, τραβώντας τον κόμβο προς τα πάνω, στη ρίζα, και σύροντας μαζί του και τις σχέσεις του.
Έτσι, το ίδιο δέντρο από την οπτική του 6 θα έμοιαζε κάπως έτσι:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Αυτό μας επιτρέπει να περιγράφουμε πιο απλά τα μονοπάτια ανάμεσα σε δύο κόμβους.
Για παράδειγμα, το μονοπάτι από το 6 στο 9 (που στο πρώτο δέντρο ανεβαίνει στη ρίζα και μετά κατεβαίνει σε ένα διαφορετικό φύλλο) φαίνεται να ακολουθεί το μονοπάτι 6-2-0-3-9.
Αυτή η άσκηση έχει να κάνει με το να πάρεις ένα δέντρο εισόδου και να το επαναπροσανατολίσεις από τη σκοπιά ενός από τους κόμβους του.
Σημειώσεις υλοποίησης
Το πρόγραμμα δοκιμών δημιουργεί δέντρα με επανειλημμένη εφαρμογή της συνάρτησης New, η οποία δέχεται μεταβλητό αριθμό ορισμάτων.
Για παράδειγμα, η εντολή
tree := New("a",New("b"),New("c",New("d")))
κατασκευάζει το παρακάτω δέντρο:
"a"
|
-------
| |
"b" "c"
|
"d"
Μπορείς να υποθέσεις ότι δεν θα υπάρχουν διπλότυπες τιμές στα δέντρα των δοκιμών.
Οι μέθοδοι Value και Children θα χρησιμοποιηθούν από το πρόγραμμα δοκιμών για την αποδόμηση των δέντρων.
Η βασική κατασκευή και αποδόμηση δέντρων πρέπει να λειτουργεί προτού ξεκινήσεις το ενδιαφέρον κομμάτι της άσκησης, γι' αυτό ελέγχεται ξεχωριστά στις τρεις πρώτες δοκιμές.
Οι μέθοδοι FromPov και PathTo είναι το ενδιαφέρον κομμάτι της άσκησης.
Η μέθοδος FromPov δέχεται ένα όρισμα συμβολοσειράς from, το οποίο προσδιορίζει έναν κόμβο του δέντρου μέσω της τιμής του.
Θα πρέπει να επιστρέφει ένα δέντρο με την τιμή from στη ρίζα.
Μπορείς να τροποποιήσεις το αρχικό δέντρο και να το επιστρέψεις, ή να δημιουργήσεις ένα νέο δέντρο και να επιστρέψεις εκείνο.
Αν επιστρέψεις ένα νέο δέντρο, είσαι ελεύθερος να καταναλώσεις ή να καταστρέψεις το αρχικό δέντρο.
Φυσικά, είναι καλό να το αφήσεις χωρίς τροποποίηση.
Η μέθοδος PathTo δέχεται δύο ορίσματα συμβολοσειράς, τα from και to, που προσδιορίζουν δύο κόμβους του δέντρου μέσω των τιμών τους.
Θα πρέπει να επιστρέφει τη συντομότερη διαδρομή στο δέντρο από τον πρώτο κόμβο στον δεύτερο.
