Διασχίσεις δέντρων (Inorder, Preorder & Postorder) με Παραδείγματα

Τι είναι το Tree Traversal;

Στη δομή δεδομένων δέντρου, η διέλευση σημαίνει επίσκεψη κόμβων με κάποιο συγκεκριμένο τρόπο. Υπάρχουν nodes2 τύποι διελεύσεων. Γενικά, αυτού του είδους η διέλευση βασίζεται στο δυαδικό δέντρο. Ένα δυαδικό δέντρο σημαίνει ότι κάθε κόμβος μπορεί να έχει το πολύ 2 κόμβους.

Ένα δυαδικό δέντρο είναι μια πολύ γνωστή δομή δεδομένων. Υπάρχει επίσης ένα δέντρο δυαδικής αναζήτησης (BST). Αυτός ο τύπος διέλευσης χρησιμοποιείται για διάφορους σκοπούς. Η διέλευση σειράς επιπέδου, χρησιμοποιείται για τον υπολογισμό του βάθους μεταξύ δύο κόμβων. Υπάρχει ένα άλλο είδος δέντρου που ονομάζεται "AVL", όπου είναι απαραίτητος ο υπολογισμός του ύψους ενός κόμβου. Μπορούμε να αναπαραστήσουμε ένα Δυαδικό δέντρο στον πίνακα, αλλά για βελτιστοποίηση μνήμης, θα χρησιμοποιήσουμε δομή και δείκτη για την αναφορά στον επόμενο κόμβο.

Τύποι διέλευσης δέντρων

Οπως συζητήσαμε δυαδικά δέντρα, τώρα συζητάμε τους επιμέρους τύπους διασχίσεων. Ανάλογα με τους τύπους, υπάρχουν δύο τύποι διέλευσης. Προηγουμένως αναφέραμε την αναγκαιότητα της σειράς επιπέδου ή της διέλευσης πλάτους-πρώτης. Τώρα Βάθος-Πρώτη Διάβαση όπως το post order χρησιμοποιείται για τη διαγραφή ενός κόμβου (θα το συζητήσουμε αργότερα), η προπαραγγελία χρησιμοποιείται για την αντιγραφή ενός Δυαδικού δέντρου και η "inorder" θα διασχίσει το δέντρο με μη φθίνουσα τρόπο.

Breadth-First Traversal
Βάθος-Πρώτη Διάβαση
Προπαραγγελία διέλευσης
Διέλευση μετά την παραγγελία
Διαδρομή κατά σειρά

Breadth-First Traversal

Είναι επίσης γνωστό ως διέλευση τάξης επιπέδου. Ας εξετάσουμε το ακόλουθο δέντρο για την επίδειξη της διέλευσης της τάξης επιπέδου.

Έτσι, θα ξεκινήσουμε από τον ριζικό κόμβο "1". Θα επισημανθεί ως επίπεδο 1. Στη συνέχεια, ο αλγόριθμος θα πάει σε όλα τα παιδιά του τρέχοντος κόμβου. Θα επισκεφτούμε τον κόμβο 2 και 3 τώρα. Θα επισημανθούν ως επίπεδο 2.

Μετά από αυτό, καθώς έχουμε 2 κόμβους στο επίπεδο 2, θα επισκεφτούμε και τα παιδιά τους. Έτσι, θα επισκεφτούμε τα 5,6,8,7 και θα τα επισημάνουμε ως επίπεδο 3. Εδώ είναι ένα πράγμα που δεν αναφέρεται,

Επίπεδο κόμβου = επίπεδο γονικού κόμβου + 1

Επίπεδο 1: 1

Επίπεδο 2: 2 3

Επίπεδο 3: 5 6 8 7

Ένας παρόμοιος αλγόριθμος χρησιμοποιείται για το BFS (Πλάτος-Πρώτη-Αναζήτηση).

Εδώ είναι ο ψευδοκώδικας για τη διέλευση σειράς επιπέδου:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Inorder Traversal Bianry Tree

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

Για ολόκληρο το δέντρο, ας πούμε ότι η ρίζα είναι 1. Τώρα θα ακολουθήσει ο αλγόριθμος:

Επισκεφθείτε το αριστερό υποδέντρο του κόμβου 1.
Ο τρέχων κόμβος είναι 2 (καθώς είναι το αριστερό υποδέντρο του 1)

Επισκεφθείτε το αριστερό υποδέντρο του 2. Ο τρέχων κόμβος θα είναι 5 αυτή τη φορά.
Μεταβαίνοντας στο 5, δεν έχει παιδιά, επομένως ο κόμβος 5 θα επισημανθεί ως επισκέψιμος. Θα επιστρέψει στον γονικό κόμβο. που είναι 2.
Καθώς γίνεται επίσκεψη στο αριστερό υποδέντρο του 2, τώρα θα γίνει επίσκεψη και στο 2.
The αλγόριθμος θα μετακινήσει τον τρέχοντα κόμβο στο δεξιό υποδέντρο του κόμβου 2, που είναι ο κόμβος 6. Μετά την επίσκεψη στον κόμβο 6. Θα μετακινηθεί στον γονικό κόμβο 2.
Καθώς γίνεται επίσκεψη στον κόμβο 2, τώρα θα επισκεφτούμε τον γονέα του 2. που είναι ο κόμβος 1.
Μετά από αυτό, θα επισκεφτούμε το σωστό υποδέντρο.

Έτσι η τελική διάβαση θα μοιάζει με αυτό:

Με σειρά: 5 → 2 → 6 → 1 → 8 → 3 → 7

Ακολουθεί ο ψευδοκώδικας για τη διέλευση κατά σειρά:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Αυτός είναι ο αναδρομικός αλγόριθμος για τη διέλευση της σειράς. Για το Δυαδικό δέντρο αναζήτησης (BST), Η διέλευση κατά σειρά δίνει τον ταξινομημένο πίνακα τιμών.

Διέλευση μετά την παραγγελία

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

Εδώ για root = 1,

Θα πάμε πρώτα στο αριστερό υποδέντρο. Άρα η ρίζα θα γίνει 2.
Τότε το 2 έχει αφήσει το υποδέντρο, οπότε θα πάμε στον κόμβο 5. Τώρα η ρίζα είναι 5.
Δεν έχει αριστερό υποδέντρο, ούτε δεξί υποδέντρο. Έτσι, τώρα θα επισημάνουμε τον κόμβο 5 ως επισκέψιμο και θα πάμε στον γονικό κόμβο του.

Τώρα η ρίζα είναι 2 και το αριστερό του υποδέντρο είναι πλήρως επισκέψιμο. Θα μετακινηθούμε τώρα στο δεξί υποδέντρο του. Άρα η ρίζα γίνεται 6.
Καθώς ο κόμβος 6 δεν έχει αριστερό και δεξί υποδέντρο, θα επισημάνουμε τον κόμβο 6 που επισκέφθηκε και θα μεταφερθούμε στον γονικό κόμβο 2.
Τώρα, γίνεται επίσκεψη τόσο στο αριστερό όσο και στο δεξί υποδέντρο για τον κόμβο 2. Θα επισημανθεί επίσης ως επισκέψιμο.
Θα μετακινηθούμε στον γονέα του κόμβου 2, που είναι ο κόμβος 1.
Το αριστερό υποδέντρο γίνεται επίσκεψη για τη ρίζα 1. Τώρα, παρόμοια, θα επισκεφτούμε το δεξί υποδέντρο.

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

Post Order: 5 → 6 → 2 → 8 → 7 → 3 → 1

Ακολουθεί ο ψευδοκώδικας για τη διέλευση μετά την παραγγελία:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

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

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

Λοιπόν, ας επιλέξουμε τον κόμβο 1 ως ρίζα.

Σύμφωνα με τον αλγόριθμο, θα ανακαλυφθεί πρώτα η ρίζα, μετά το αριστερό και μετά το δεξί υποδέντρο.
Έτσι, θα επισκεφτούμε τη ρίζα 1. Στη συνέχεια θα μετακινηθούμε στο αριστερό υποδέντρο της. Η ρίζα γίνεται 2.
Θα επισκεφτούμε τον κόμβο 2 και θα μετακινηθούμε στο αριστερό υποδέντρο του. Έτσι, η ρίζα γίνεται 3.
Επισκεπτόμαστε τον κόμβο 3 και μετά μεταβαίνουμε στον γονικό κόμβο του. Τώρα γίνεται επίσκεψη στον κόμβο 2 και στο αριστερό του υποδέντρο. Ώρα για επίσκεψη στο σωστό υποδέντρο.
Θα μετακινηθούμε στο δεξί υποδέντρο, η ρίζα γίνεται 4. Θα επισκεφτούμε το 4. Καθώς το 4 δεν έχει θυγατρικό κόμβο, θα μεταφερθούμε στον γονέα του.
Τώρα η ρίζα είναι 2 και γίνεται επίσκεψη μαζί με το αριστερό και το δεξί υποδέντρο της. Έτσι, θα μεταφερθούμε στον γονικό κόμβο του. Τώρα η ρίζα γίνεται 1.
Ομοίως, θα επισκεφτούμε το σωστό υποδέντρο.

Προπαραγγελία: 1 → 2 → 3 → 4 → 5 → 6 → 7

Ακολουθεί ο ψευδοκώδικας για τη διέλευση μετά την παραγγελία:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Εφαρμογή στο Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Παραγωγή:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Εφαρμογή στο Γ

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}