Εναλλακτική τοποθέτηση κόμβων σε ίδια δομή binary search tree.

[Ilias95]

Έχω την παρακάτω άσκηση:

 

Έπειτα από σκέψη συνειδητοποίησα ότι μπορώ εύκολα να πάρω την τελική δομή του δέντρου χάρη στην ιδιότητα της inorder διέλευσης να εμφανίζει τα δεδομένα ταξινομημένα. Αρκεί να επισκεφτώ έναν-έναν τους κόμβους του δέντρου με την inorder traversal και να τοποθετώ τα νούμερα σε αύξουσα σειρά.

Μετά, αφού έχω την τελική δομή του δέντρου, παρατήρησα ότι αρκεί να εφαρμόσω την preorder traversal και το αποτέλεσμα της θα είναι η μία απ' τις δύο σειρές εισαγωγής που ζητάει.

Αυτό που δεν καταλαβαίνω απ' την άσκηση και δεν το καθιστά σαφές και η εκφώνηση νομίζω, είναι αν θέλει απλά δύο διαφορετικές σειρές εισαγωγής με τις οποίες τελικά να προκύπτει το ίδιο ακριβώς δέντρο ή πρέπει και το τελικό αποτέλεσμα να είναι διαφορετικό. Είναι δηλαδή δυνατόν να τοποθετήσω με διαφορετικό τρόπο τα στοιχεία σε μια συγκεκριμένη δομή ενός binary search tree;

Αν δεν θέλει το δεύτερο τότε αρκεί νομίζω να εκτελέσω πάλι την preorder αλλάζοντας την σειρά επίσκεψης από left, right σε right, left και θα έχω διαφορετική σειρά εισαγωγής και το ίδιο τελικό δέντρο.

Επίσης υπάρχει κάποια στανταρτ μεθοδολογία για την επίλυση του συγκεκριμένου προβλήματος;

[chigal]

Το τελικό αποτέλεσμα δε μπορεί να είναι διαφορετικό. Εξ ορισμού, τα στοιχεία σε κάθε αριστερό υποδέντρο είναι μικρότερα της ρίζας και του δεξιού είναι μεγαλύτερα. Εφόσον, πχ. έχουμε 4 στοιχεία αριστερά της ρίζας και 5 δεξιά, το 35 θα είναι αναγκαστικά η κεφαλή. Ομοίως μπορείς να χτίσεις και το υπόλοιπο δέντρο (αν και η μέθοδός σου με την inorder traversal είναι πιο κομψή νομίζω, ή τουλάχιστον όχι τόσο μπακαλίστικη).

 

Όσο για τη σειρά  εισαγωγής των στοιχείων, νομίζω αυτό που προτείνεις είναι η μόνη λύση. Κάθε ρίζα υποδέντρου πρέπει να εισαχθεί οπωσδήποτε πριν από το αριστερό της παιδί (γιατί αν μπει πρώτα το παιδί, τότε η "ρίζα" θα πρέπει μετά να είναι κάπου δεξιά του) και πριν από το δεξί της παιδί (γιατί αν μπει πρώτα το παιδί, τότε η "ρίζα" θα πρέπει μετά να είναι κάπου αριστερά του). Η μόνη ευελιξία που υπάρχει είναι ανάμεσα σε αδέλφια - αν θα μπει πρώτο το ένα ή το άλλο, αφου βέβαια έχει πρώτα μπει ο γονιός.

[Ilias95]

Ναι, εκεί κατέληξα τελικά κι εγώ.
Ευχαριστώ πολύ για την απάντηση.