इस ट्यूटोरियल में, आप विभिन्न ट्री ट्रैवर्सल तकनीकों के बारे में जानेंगे। इसके अलावा, आपको C, C ++, Java और पायथन में विभिन्न ट्री ट्रैवर्सल तरीकों के काम करने के उदाहरण मिलेंगे।
एक पेड़ को हटाने का मतलब है कि पेड़ में प्रत्येक नोड का दौरा करना। उदाहरण के लिए, आप पेड़ में सभी मूल्यों को जोड़ना चाहते हैं या सबसे बड़ा खोज सकते हैं। इन सभी कार्यों के लिए, आपको पेड़ के प्रत्येक नोड पर जाना होगा।
रैखिक डेटा संरचनाएं जैसे सरणियाँ, ढेर, कतारें और लिंक की गई सूची में डेटा पढ़ने का केवल एक ही तरीका है। लेकिन एक पेड़ की तरह एक पदानुक्रमित डेटा संरचना को विभिन्न तरीकों से ट्रेस किया जा सकता है।
पेड़ का फंदा
आइए विचार करें कि हम ऊपर दिखाए गए चित्र में पेड़ के तत्वों को कैसे पढ़ सकते हैं।
ऊपर से शुरू, बाएं से दाएं
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)
त्राटक का alभ्यास
- रूट नोड पर जाएं
- बाईं सबट्री में सभी नोड्स पर जाएँ
- सही सबट्री में सभी नोड्स पर जाएँ
display(root->data) preorder(root->left) preorder(root->right)
पोस्टऑर्डर ट्रैवर्सल
- बाईं सबट्री में सभी नोड्स पर जाएँ
- सही सबट्री में सभी नोड्स पर जाएँ
- रूट नोड पर जाएँ
postorder(root->left) postorder(root->right) display(root->data)
आइए ऑर्डर-इन ट्रैवर्सल की कल्पना करें। हम रूट नोड से शुरू करते हैं।
लेफ्ट और राइट सबट्री
हम पहले बाएं सबट्री को पार करते हैं। हमें रूट नोड और सही सबट्री का दौरा करने के लिए याद रखना होगा जब यह पेड़ किया जाता है।
चलो यह सब एक स्टैक में डालते हैं ताकि हम याद रखें।
ढेर
अब हम स्टैक के टॉप पर बताए गए सबट्री की ओर बढ़ते हैं।
फिर से, हम इन्वर्टर के उसी नियम का पालन करते हैं
बायाँ सबट्री -> रूट -> राईट सबट्री
बाईं सबट्री को ट्रेस करने के बाद, हमें छोड़ दिया जाता है
फाइनल स्टैक
चूंकि नोड "5" में कोई उपप्रकार नहीं है, हम इसे सीधे प्रिंट करते हैं। उसके बाद हम उसके माता-पिता को "12" और फिर सही बच्चे को "6" प्रिंट करते हैं।
एक स्टैक पर सब कुछ डालना मददगार था क्योंकि अब रूट नोड के बाएं सबट्री को ट्रैवर्स किया गया है, हम इसे प्रिंट कर सकते हैं और राइट सबट्री पर जा सकते हैं।
सभी तत्वों के माध्यम से जाने के बाद, हमें इनवर्टर ट्रावेल के रूप में मिलता है
5 -> 12 -> 6 -> 1 -> 9
हमें खुद को स्टैक बनाने की आवश्यकता नहीं है क्योंकि पुनरावृत्ति हमारे लिए सही क्रम बनाए रखती है।
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी + # 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);
