Οδηγίες
Άλλαξε τη ρίζα ενός δέντρου σε έναν επιλεγμένο κόμβο.
Ένα δέντρο είναι ένας ειδικός τύπος γράφου, όπου όλοι οι κόμβοι είναι συνδεδεμένοι αλλά δεν υπάρχουν κύκλοι.
Αυτό σημαίνει ότι υπάρχει ακριβώς ένα μονοπάτι για να πας από έναν κόμβο σε έναν άλλο, για οποιοδήποτε ζεύγος κόμβων.
Αυτή η άσκηση έχει να κάνει με τον επαναπροσανατολισμό ενός δέντρου, ώστε να δεις τα πράγματα από μια διαφορετική οπτική γωνία.
Για παράδειγμα, τα οικογενειακά δέντρα παρουσιάζονται συνήθως από την οπτική του προγόνου:
+------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.
Αυτή η άσκηση έχει να κάνει με το να πάρεις ένα δέντρο εισόδου και να το επαναπροσανατολίσεις από τη σκοπιά ενός από τους κόμβους του.
Σημειώσεις υλοποίησης
Το αντικείμενο Tree έχει δύο χαρακτηριστικά:
-
String label
-
List<Tree> children
Το δοκιμαστικό πρόγραμμα δημιουργεί δέντρα με επαναλαμβανόμενη εφαρμογή της συνάρτησης δημιουργίας Tree.of. Για παράδειγμα, η εντολή
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
κατασκευάζει το ακόλουθο δέντρο:
"a"
|
-------
| |
"b" "c"
|
"d"
Μπορείς να υποθέσεις ότι δε θα υπάρχουν διπλότυπες τιμές στα δέντρα δοκιμών.
Οι μέθοδοι FromPov και PathTo είναι το ενδιαφέρον κομμάτι της άσκησης.
Η μέθοδος FromPov δέχεται ένα όρισμα συμβολοσειράς from που προσδιορίζει έναν κόμβο στο δέντρο μέσω της τιμής του. Θα πρέπει να επιστρέφει ένα δέντρο με την τιμή from στη ρίζα. Μπορείς να τροποποιήσεις το αρχικό δέντρο και να το επιστρέψεις ή να δημιουργήσεις ένα νέο δέντρο και να επιστρέψεις αυτό. Αν επιστρέψεις ένα νέο δέντρο, είσαι ελεύθερος να καταναλώσεις ή να καταστρέψεις το αρχικό δέντρο. Φυσικά, είναι καλό να το αφήσεις αμετάβλητο.
Η μέθοδος PathTo δέχεται δύο ορίσματα συμβολοσειρών from και to που προσδιορίζουν δύο κόμβους στο δέντρο μέσω των τιμών τους. Θα πρέπει να επιστρέφει τη συντομότερη διαδρομή στο δέντρο από τον πρώτο στον δεύτερο κόμβο.
Μηνύματα εξαιρέσεων
Μερικές φορές είναι απαραίτητο να πετάξεις μια εξαίρεση. Όταν το κάνεις αυτό, θα πρέπει πάντα να συμπεριλαμβάνεις ένα κατατοπιστικό μήνυμα σφάλματος για να υποδείξεις ποια είναι η πηγή του σφάλματος. Αυτό κάνει τον κώδικά σου πιο ευανάγνωστο και βοηθά σημαντικά στην αποσφαλμάτωση.
Αυτή η συγκεκριμένη άσκηση απαιτεί να χρησιμοποιήσεις τη λέξη-κλειδί throw για να πετάξεις πολλαπλές UnsupportedOperationException αν η κλάση Tree() δεχθεί ένα δέντρο που δε μπορεί να επαναπροσανατολιστεί, ή αν δε μπορεί να βρεθεί μια διαδρομή μεταξύ ενός start node και ενός end node. Τα τεστ θα περάσουν μόνο αν και throw την exception και συμπεριλάβεις ένα μήνυμα μαζί της.
Για να πετάξεις μια UnsupportedOperationException με ένα μήνυμα, γράψε το μήνυμα ως όρισμα στον τύπο exception:
// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");
// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");
