Υπάρχουν περισσότεροι από ένας τρόποι για να επισκεφθείτε όλους τους κόμβους σε ένα BST.

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

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

Inorder Traversal

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

instagram viewer

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

Αλγόριθμος διέλευσης εντολών

Επαναλάβετε για να διασχίσετε όλους τους κόμβους του BST:

  1. Διασχίστε αναδρομικά το αριστερό υποδέντρο.
  2. Επισκεφθείτε τον ριζικό κόμβο.
  3. Διασχίστε αναδρομικά το δεξί υποδέντρο.

Οπτικοποίηση Inorder Traversal

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

Σε αυτό το δυαδικό δέντρο αναζήτησης, το 56 είναι ο ριζικός κόμβος. Πρώτα, πρέπει να διασχίσετε το αριστερό υποδέντρο 32, μετά τον ριζικό κόμβο 56 και μετά το δεξί υποδέντρο 62.

Για το υποδέντρο 32, διασχίστε πρώτα το αριστερό υποδέντρο, 28. Αυτό το υποδέντρο δεν έχει παιδιά, οπότε στη συνέχεια διασχίστε τον κόμβο 32. Στη συνέχεια, διασχίστε το δεξί υποδέντρο, 44, το οποίο επίσης δεν έχει παιδιά. Επομένως, η σειρά διέλευσης για το υποδέντρο που έχει ρίζες στο 32 είναι 28 -> 32 -> 44.

Στη συνέχεια, επισκεφτείτε τον ριζικό κόμβο, 56.

Στη συνέχεια, διασχίστε το δεξί υποδέντρο, με ρίζες στο 62. Ξεκινήστε διασχίζοντας το αριστερό του υποδέντρο, με ρίζες στο 58. Δεν έχει παιδιά, οπότε επισκεφθείτε τον κόμβο 62 στη συνέχεια. Τέλος, περάστε το δεξί υποδέντρο, το 88, το οποίο επίσης δεν έχει παιδιά.

Έτσι, ο αλγόριθμος επισκέπτεται τους κόμβους του δέντρου με την ακόλουθη σειρά:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Εφαρμογή Inorder Traversal

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

Προπαραγγελία διέλευσης

Η διέλευση προπαραγγελίας είναι παρόμοια με την inorder, αλλά επεξεργάζεται τον ριζικό κόμβο πριν επεξεργαστεί αναδρομικά το αριστερό υποδέντρο και μετά το δεξί υποδέντρο.

Αλγόριθμος διέλευσης προπαραγγελίας

Επαναλάβετε για να διασχίσετε όλους τους κόμβους του BST:

  1. Επισκεφθείτε τον ριζικό κόμβο.
  2. Διασχίστε αναδρομικά το αριστερό υποδέντρο.
  3. Διασχίστε αναδρομικά το δεξί υποδέντρο.

Οπτικοποίηση της διέλευσης προπαραγγελίας

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

Σε αυτό το δυαδικό δέντρο αναζήτησης, ξεκινήστε με την επεξεργασία του ριζικού κόμβου, 56. Στη συνέχεια, διασχίστε το αριστερό υποδέντρο, 32, ακολουθούμενο από το δεξί υποδέντρο, 62.

Για το αριστερό υποδέντρο, επεξεργαστείτε την τιμή στον ριζικό κόμβο, 32. Στη συνέχεια, διασχίστε το αριστερό υποδέντρο, 28 και, τέλος, το δεξί υποδέντρο, 44. Αυτό ολοκληρώνει τη διέλευση του αριστερού υποδέντρου με ρίζες στο 32. Η διέλευση γίνεται με την ακόλουθη σειρά: 56 -> 32 -> 28 -> 44.

Για το δεξί υποδέντρο, επεξεργαστείτε την τιμή στον ριζικό κόμβο, 62. Στη συνέχεια, διασχίστε το αριστερό υποδέντρο, 58 και, τέλος, το δεξί υποδέντρο, 88. Και πάλι, κανένας κόμβος δεν έχει παιδιά, επομένως η διέλευση ολοκληρώνεται σε αυτό το σημείο.

Έχετε διασχίσει το πλήρες δέντρο με την ακόλουθη σειρά:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

Εφαρμογή διέλευσης προπαραγγελίας

Μπορείτε να χρησιμοποιήσετε τη διέλευση προπαραγγελίας για να δημιουργήσετε πιο εύκολα ένα αντίγραφο του δέντρου.

Διέλευση ταχυδρομικής παραγγελίας

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

Αλγόριθμος διέλευσης μετά παραγγελία

Επαναλάβετε για να διασχίσετε όλους τους κόμβους του BST:

  1. Διασχίστε αναδρομικά το αριστερό υποδέντρο.
  2. Διασχίστε αναδρομικά το δεξί υποδέντρο.
  3. Επισκεφθείτε τον ριζικό κόμβο.

Οπτικοποίηση της διέλευσης μετά παραγγελία

Το παρακάτω σχήμα δείχνει τη διέλευση ταχυδρομικών παραγγελιών του δέντρου δυαδικής αναζήτησης:

Ξεκινήστε διασχίζοντας το αριστερό υποδέντρο, 32, και μετά το δεξί υποδέντρο, 62. Ολοκληρώστε με την επεξεργασία του ριζικού κόμβου, 56.

Για να επεξεργαστείτε το υποδέντρο, που έχει ρίζες στο 32, διασχίστε το αριστερό του υποδέντρο, 28. Επειδή το 28 δεν έχει παιδιά, μετακινηθείτε στο δεξί υποδέντρο, 44. Διαδικασία 44 αφού επίσης δεν έχει παιδιά. Τέλος, επεξεργαστείτε τον ριζικό κόμβο, 32. Έχετε διασχίσει αυτό το υποδέντρο με τη σειρά 28 -> 44 -> 32.

Επεξεργαστείτε το δεξί υποδέντρο χρησιμοποιώντας την ίδια προσέγγιση για να επισκεφθείτε κόμβους με τη σειρά 58 -> 88 → 62.

Τέλος, επεξεργαστείτε τον ριζικό κόμβο, 56. Θα διασχίσετε το πλήρες δέντρο με αυτή τη σειρά:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

Εφαρμογή Postorder Traversal

Μπορείτε να χρησιμοποιήσετε τη διέλευση postorder για να διαγράψετε ένα δέντρο από φύλλο σε ρίζα. Μπορείτε επίσης να το χρησιμοποιήσετε για να βρείτε την έκφραση postfix ενός δέντρου έκφρασης.

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

Χρονική και χωρική πολυπλοκότητα των δυαδικών διασχίσεων δέντρων αναζήτησης

Η χρονική πολυπλοκότητα και των τριών τεχνικών διέλευσης είναι Επί), που n είναι το μέγεθος του δυαδικό δέντρο. Η πολυπλοκότητα του χώρου όλων των τεχνικών διέλευσης είναι Ο(η), που η είναι το ύψος του δυαδικού δέντρου.

Το μέγεθος του δυαδικού δέντρου είναι ίσο με τον αριθμό των κόμβων σε αυτό το δέντρο. Το ύψος του δυαδικού δέντρου είναι ο αριθμός των άκρων μεταξύ του ριζικού κόμβου του δέντρου και του πιο απομακρυσμένου κόμβου φύλλων του.

Κώδικας Python για διέλευση δέντρου δυαδικής αναζήτησης

Παρακάτω είναι ένα πρόγραμμα Python για την εκτέλεση και των τριών δυαδικών διασχίσεων δέντρων αναζήτησης:

# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
definorder(root):
 if root:
# Traverse left subtree
inorder(root.left)


# Traverse root
print(str(root.value) + ", ", end='')


# Traverse right subtree
inorder(root.right)


# Function to perform the postorder tree traversal
defpostorder(root):
 if root:
# Traverse left subtree
postorder(root.left)


# Traverse right subtree
postorder(root.right)


# Traverse root
print(str(root.value) + ", ", end='')


# Function to perform the preorder tree traversal
defpreorder(root):
 if root:
# Traverse root
print(str(root.value) + ", ", end='')


# Traverse left subtree
preorder(root.left)


# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

Αυτό το πρόγραμμα θα πρέπει να παράγει την ακόλουθη έξοδο:

Must-know αλγόριθμοι για προγραμματιστές

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