Σε αυτό το σεμινάριο, θα μάθετε για διαφορετικές τεχνικές διαφυγής δέντρων. Επίσης, θα βρείτε λειτουργικά παραδείγματα διαφορετικών μεθόδων διέλευσης δέντρων σε C, C ++, Java και Python.
Διασχίζοντας ένα δέντρο σημαίνει να επισκέπτεστε κάθε κόμβο του δέντρου. Για παράδειγμα, ίσως θέλετε να προσθέσετε όλες τις τιμές στο δέντρο ή να βρείτε τη μεγαλύτερη. Για όλες αυτές τις λειτουργίες, θα πρέπει να επισκεφτείτε κάθε κόμβο του δέντρου.
Οι γραμμικές δομές δεδομένων όπως πίνακες, στοίβες, ουρές και συνδεδεμένη λίστα έχουν μόνο έναν τρόπο ανάγνωσης των δεδομένων. Αλλά μια ιεραρχική δομή δεδομένων όπως ένα δέντρο μπορεί να διασχίζεται με διαφορετικούς τρόπους.
Διασχίζοντας το δέντρο
Ας σκεφτούμε πώς μπορούμε να διαβάσουμε τα στοιχεία του δέντρου στην εικόνα που φαίνεται παραπάνω.
Ξεκινώντας από πάνω, από αριστερά προς τα δεξιά
1 -> 12 -> 5 -> 6 -> 9
Ξεκινώντας από κάτω, από αριστερά προς τα δεξιά
5 -> 6 -> 12 -> 9 -> 1
Αν και αυτή η διαδικασία είναι κάπως εύκολη, δεν σέβεται την ιεραρχία του δέντρου, αλλά μόνο το βάθος των κόμβων.
Αντ 'αυτού, χρησιμοποιούμε διασταυρούμενες μεθόδους που λαμβάνουν υπόψη τη βασική δομή ενός δέντρου, δηλαδή
struct node ( int data; struct node* left; struct node* right; )
Ο δομικός κόμβος που υποδεικνύεται από αριστερά και δεξιά μπορεί να έχει άλλα αριστερά και δεξιά παιδιά, οπότε πρέπει να τα θεωρούμε ως υποδέντρα αντί για υπο-κόμβους.
Σύμφωνα με αυτή τη δομή, κάθε δέντρο είναι ένας συνδυασμός
- Ένας κόμβος που μεταφέρει δεδομένα
- Δύο υποδέντρα
Αριστερό και Δεξιό Υπόγειο
Θυμηθείτε ότι ο στόχος μας είναι να επισκεφτείτε κάθε κόμβο, επομένως πρέπει να επισκεφτούμε όλους τους κόμβους στο υποδένδρο, να επισκεφτούμε τον ριζικό κόμβο και να επισκεφτούμε όλους τους κόμβους στο δεξιό υποδένδρο.
Ανάλογα με τη σειρά με την οποία το κάνουμε αυτό, μπορεί να υπάρχουν τρεις τύποι διέλευσης.
Διαδρομή εντός της γραμμής
- Αρχικά, επισκεφτείτε όλους τους κόμβους στο αριστερό υποδένδρο
- Τότε ο ριζικός κόμβος
- Επισκεφτείτε όλους τους κόμβους στο σωστό υποδένδρο
inorder(root->left) display(root->data) inorder(root->right)
Προπαραγγελία διέλευσης
- Επισκεφτείτε τον ριζικό κόμβο
- Επισκεφτείτε όλους τους κόμβους στο αριστερό υποδένδρο
- Επισκεφτείτε όλους τους κόμβους στο σωστό υποδένδρο
display(root->data) preorder(root->left) preorder(root->right)
Διασυνοριακή μετάβαση
- Επισκεφτείτε όλους τους κόμβους στο αριστερό υποδένδρο
- Επισκεφτείτε όλους τους κόμβους στο σωστό υποδένδρο
- Επισκεφτείτε τον ριζικό κόμβο
postorder(root->left) postorder(root->right) display(root->data)
Ας απεικονίσουμε διασταυρούμενη σειρά. Ξεκινάμε από τον ριζικό κόμβο.
Αριστερό και Δεξιό Υπόγειο
Διασχίζουμε πρώτα το αριστερό υπόστρωμα. Πρέπει επίσης να θυμόμαστε να επισκεφτούμε τον ριζικό κόμβο και το σωστό υποδένδρο όταν τελειώσει αυτό το δέντρο.
Ας τα βάλουμε όλα αυτά σε μια στοίβα για να θυμόμαστε.
Σωρός
Τώρα διασχίζουμε το υποδένδρο που δείχνει στο TOP της στοίβας.
Και πάλι, ακολουθούμε τον ίδιο κανόνα inorder
Αριστερό υποδένδρο -> ρίζα -> δεξιό υποδένδρο
Αφού διασχίσουμε το αριστερό υποδένδρο, μένουμε μαζί
Τελική στοίβα
Επειδή ο κόμβος "5" δεν έχει δευτερεύοντα δέντρα, το εκτυπώνουμε απευθείας. Μετά από αυτό εκτυπώνουμε τον γονέα του "12" και μετά το σωστό παιδί "6".
Η τοποθέτηση όλων σε μια στοίβα ήταν χρήσιμη, διότι τώρα που διασχίστηκε το αριστερό-υπόστρωμα του ριζικού κόμβου, μπορούμε να το εκτυπώσουμε και να πάμε στο σωστό υποδένδρο.
Αφού εξετάσουμε όλα τα στοιχεία, παίρνουμε το inorder traversal ως
5 -> 12 -> 6 -> 1 -> 9
Δεν χρειάζεται να δημιουργήσουμε οι ίδιοι τη στοίβα γιατί η αναδρομή διατηρεί τη σωστή σειρά για εμάς.
Παραδείγματα Python, Java και C / C ++
Python Java C C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
