Η κατανόηση αυτών των μεθόδων είναι απαραίτητη για διάφορες εφαρμογές όπως η αναζήτηση, διαλογή και αξιολόγηση έκφρασης. Αυτό το άρθρο συγκρίνει τις τρεις κύριες μεθόδους διέλευσης: την προπαραγγελία, την τάξη και τη μεταδιάταξη, με πρακτικούς υπολογισμούς για να απεικονίσουν τις διαφορές τους.

Προδιατακτική Traversal

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

Για παράδειγμα, δεδομένου του δέντρου:

A
/
B C
/
D E F

Η προπαραγγελία διαπεραστική ακολουθία είναι: A, B, D, E, C, F.

Διατάξτε Traversal

Η σειρά traversal επισκέπτεται το αριστερό υποδέντρο πρώτα, μετά ο ριζικός κόμβος, και τέλος το δεξί υποδέντρο. Αυτή η μέθοδος χρησιμοποιείται συνήθως για δυαδική δέντρα αναζήτησης για την ανάκτηση δεδομένων με ταξινομημένη σειρά.

Χρησιμοποιώντας το ίδιο δέντρο, η αδιάτακτη εγκάρσια ακολουθία είναι: D, B, E, A, C, F.

Μεταδιατάξεις Traversal

Μετά την εντολή traversal επισκέπτεται το αριστερό υποδέντρο, στη συνέχεια το δεξί υποδέντρο, και τέλος ο κόμβος ρίζας. Αυτή η προσέγγιση είναι χρήσιμη για τη διαγραφή των δέντρων ή την αξιολόγηση μετα-fix εκφράσεις.

Για παράδειγμα δέντρο, η μεταπαραγγελία διαπεραστική ακολουθία είναι: D, E, B, F, C, A.

Πρακτικοί υπολογισμοί

Σκεφτείτε το δέντρο:

1
/
2 3
/
4 5 6

Διατομή: 1, 2, 4, 5, 3, 6

Διατάξτε το εγκάρσιο: 4, 2, 5, 1, 3, 6

Μετά την εντολή διατομής: 4, 5, 2, 6, 3, 1