जावास्क्रिप्ट में ट्री ट्रैवर्सल की खोज: उदाहरणों के साथ इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर

ट्री ट्रैवर्सल कंप्यूटर विज्ञान में एक मौलिक अवधारणा है जिसमें ट्री डेटा संरचना में व्यवस्थित रूप से प्रत्येक नोड पर जाना शामिल है। ट्री ट्रैवर्सल के माध्यम से, हम पूर्व निर्धारित क्रम में नोड्स को प्रोसेस कर सकते हैं, जिससे खोज, छँटाई और भावों का मूल्यांकन करने जैसे कार्यों को सुगम बनाया जा सकता है।

इस लेख में, हम तीन सबसे व्यापक रूप से उपयोग किए जाने वाले ट्री ट्रैवर्सल विधियों का पता लगाएंगे: इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर।

जावास्क्रिप्ट में कार्यान्वित स्पष्ट और संक्षिप्त उदाहरणों के माध्यम से, आप इन ट्रैवर्सल तकनीकों की ठोस समझ प्राप्त करेंगे।

वृक्ष संरचना परिभाषा

ट्री ट्रैवर्सल एल्गोरिदम में गोता लगाने से पहले, आइए उस संरचना को परिभाषित करें जिसका उपयोग हम बाइनरी ट्री के लिए करेंगे। पेड़ में नोड्स शामिल होंगे, जहां प्रत्येक नोड में इसके बाएं और दाएं बच्चे के नोड्स के मूल्य और संदर्भ होते हैं।

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

अब जब हमने ट्री स्ट्रक्चर को परिभाषित कर लिया है, तो हम तीन ट्री ट्रैवर्सल विधियों की खोज के साथ आगे बढ़ सकते हैं।

इनऑर्डर ट्रैवर्सल

इनऑर्डर ट्रैवर्सल बाइनरी ट्री में विज़िटिंग नोड्स के अगले पैटर्न का अनुसरण करता है - एल्गोरिथम पहले बाएं सबट्री को ट्रैवर्स करता है, फिर वर्तमान नोड पर जाता है, और अंत में राइट सबट्री को ट्रैवर्स करता है। यह सुनिश्चित करता है कि यदि पेड़ एक क्रमबद्ध डेटा संरचना का प्रतिनिधित्व करता है तो नोड्स को आरोही क्रम में देखा जाता है।

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

रिकर्सिव इनऑर्डर ट्रैवर्सल

1. जांचें कि क्या वर्तमान नोड शून्य है। यदि ऐसा है, तो लौट आओ।

   
   

2. फ़ंक्शन को बाएं सबट्री पर पुनरावर्ती रूप से कॉल करें।

   
   

3. वर्तमान नोड पर जाएँ।

   
   

4. फ़ंक्शन को पुनरावर्ती रूप से सही सबट्री पर कॉल करें।

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

गैर-पुनरावर्ती इनऑर्डर ट्रैवर्सल

1. एक खाली ढेर को प्रारंभ करें, और वर्तमान नोड को पेड़ की जड़ पर सेट करें।

   
   

2. जब स्टैक खाली न हो या वर्तमान नोड शून्य न हो, तब पुनरावृति करें।

   • एक अशक्त बाएँ बच्चे तक पहुँचने तक सभी बाएँ नोड्स को स्टैक पर पुश करें।

   • स्टैक से एक नोड पॉप करें, उस पर जाएं, और वर्तमान नोड को उसके दाहिने बच्चे पर सेट करें।

     
     

3. स्टैक खाली होने तक चरण 2 को दोहराएं और वर्तमान नोड शून्य है।

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

प्रीऑर्डर ट्रैवर्सल

प्रीऑर्डर ट्रैवर्सल में, एल्गोरिथ्म पहले वर्तमान नोड पर जाता है, फिर बाएं सबट्री को ट्रेस करता है, और अंत में राइट सबट्री को ट्रैवर्स करता है। यह क्रम सुनिश्चित करता है कि नोड्स को "टॉप-डाउन" तरीके से देखा जाता है, जड़ से शुरू होकर पत्तियों की ओर बढ़ता है।

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

रिकर्सिव प्रीऑर्डर ट्रैवर्सल

1. जांचें कि क्या वर्तमान नोड शून्य है। यदि ऐसा है, तो लौट आओ।

   
   

2. वर्तमान नोड पर जाएँ।

   
   

3. फ़ंक्शन को बाएं सबट्री पर पुनरावर्ती रूप से कॉल करें।

   
   

4. फ़ंक्शन को पुनरावर्ती रूप से सही सबट्री पर कॉल करें।

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

गैर-पुनरावर्ती प्रीऑर्डर ट्रैवर्सल

1. खाली स्टैक से शुरू करें, और रूट नोड को स्टैक पर धकेलें।

   
   

2. प्रीऑर्डर ट्रैवर्सल रिजल्ट को स्टोर करने के लिए एक खाली एरे को इनिशियलाइज़ करें।

   
   

3. थोड़ी देर का लूप दर्ज करें जो स्टैक के खाली होने तक चलता है।

   
   

4. स्टैक से एक नोड पॉप करें, और परिणाम सरणी में इसका मान जोड़कर उस पर जाएँ।

   
   

5. यदि नोड का एक सही बच्चा है, तो सही बच्चे को स्टैक पर धकेलें।

   
   

6. यदि नोड में बायाँ सन्तान है, तो बाएँ सन्तान को स्टैक पर धकेलें।

   
   

7. स्टैक खाली होने तक चरण 3-6 दोहराएं।

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

पोस्टऑर्डर ट्रैवर्सल

इस ट्रैवर्सल में, एल्गोरिथम पहले बाएं सबट्री को ट्रैवर्स करता है, फिर राइट सबट्री, और अंत में वर्तमान नोड पर जाता है। यह क्रम सुनिश्चित करता है कि नोड्स को "बॉटम-अप" तरीके से देखा जाता है, पत्तियों से शुरू होकर रूट की ओर बढ़ता है।

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

रिकर्सिव पोस्टऑर्डर ट्रैवर्सल

1. जांचें कि क्या वर्तमान नोड शून्य है। यदि ऐसा है, तो लौट आओ।

   
   

2. फ़ंक्शन को बाएं सबट्री पर पुनरावर्ती रूप से कॉल करें।

   
   

3. फ़ंक्शन को पुनरावर्ती रूप से सही सबट्री पर कॉल करें।

   
   

4. वर्तमान नोड पर जाएँ।

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

गैर-पुनरावर्ती पोस्टऑर्डर ट्रैवर्सल

1. खाली स्टैक से शुरू करें, और रूट नोड को स्टैक पर धकेलें।

   
   

2. पोस्टऑर्डर ट्रैवर्सल परिणाम को स्टोर करने के लिए एक खाली ऐरे को इनिशियलाइज़ करें।

   
   

3. थोड़ी देर का लूप दर्ज करें जो स्टैक के खाली होने तक चलता है।

   
   

4. स्टैक से शीर्ष नोड प्राप्त करें (इसे हटाए बिना)।

   
   

5. यदि नोड में एक बायाँ बच्चा है, तो बाएँ बच्चे को ढेर पर धकेलें, और वर्तमान नोड के बाएँ बच्चे को शून्य पर सेट करें।

   
   

6. यदि नोड का एक सही बच्चा है, तो सही बच्चे को स्टैक पर धकेलें, और वर्तमान नोड के सही बच्चे को शून्य पर सेट करें।

   
   

7. यदि नोड में न तो बाएँ और न ही दाएँ बच्चे हैं, तो यह एक पत्ता नोड है। नोड को स्टैक से पॉप करें, और इसके मान को परिणाम सरणी में जोड़ें।

   
   

8. स्टैक खाली होने तक चरण 4-7 दोहराएं।

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

निष्कर्ष

मुझे उम्मीद है कि अब आपको जावास्क्रिप्ट में इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल के बीच के अंतर की स्पष्ट समझ हो गई है। प्रदान किए गए ज्ञान और उदाहरणों के साथ, अब आप इन तकनीकों को अपने कार्यों और परियोजनाओं में प्रभावी ढंग से लागू करने के लिए सुसज्जित हैं।