डेटा संरचना और एल्गोरिदम - ट्री ट्रैवर्सल

ट्रावर्सल एक पेड़ के सभी नोड्स का दौरा करने की एक प्रक्रिया है और उनके मूल्यों को भी मुद्रित कर सकता है। क्योंकि, सभी नोड्स किनारों (लिंक) के माध्यम से जुड़े होते हैं, हम हमेशा रूट (हेड) नोड से शुरू करते हैं। यही है, हम एक पेड़ में एक नोड को बेतरतीब ढंग से एक्सेस नहीं कर सकते हैं। एक पेड़ को पार करने के लिए तीन तरीके हैं -

• इन-ऑर्डर ट्रैवर्सल
• ट्रैवर्सल को प्री-ऑर्डर करें
• पोस्ट-ऑर्डर ट्रैवर्सल

आम तौर पर, हम किसी दिए गए आइटम या कुंजी को पेड़ में खोजने या उसका पता लगाने के लिए या उसमें मौजूद सभी मूल्यों को प्रिंट करने के लिए एक पेड़ पर चढ़ते हैं।

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

इस त्रैमासिक विधि में, बाएं उपप्रकार का दौरा पहले किया जाता है, फिर मूल और बाद में दाएं उप-पेड़। हमें हमेशा याद रखना चाहिए कि प्रत्येक नोड एक उपप्रकार का प्रतिनिधित्व कर सकता है।

यदि एक द्विआधारी वृक्ष का पता लगाया जाता है in-orderआउटपुट एक आरोही क्रम में प्रमुख मानों को हल करेगा।

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

D → B → E → A → F → C → G

कलन विधि

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

ट्रैवर्सल को प्री-ऑर्डर करें

इस ट्रैवर्सल विधि में, रूट नोड का दौरा पहले किया जाता है, फिर बाएं सबट्री और अंत में राइट सबट्री।

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

A → B → D → E → C → F → G

कलन विधि

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

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

इस ट्रैवर्सल विधि में, रूट नोड को अंतिम बार देखा जाता है, इसलिए नाम। पहले हम बाएं सबट्री को फंसाते हैं, फिर राइट सबट्री और आखिर में रूट नोड को।

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

D → E → B → F → G → C → A

कलन विधि

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

ट्री ट्रैवर्सिंग के सी कार्यान्वयन की जांच करने के लिए, कृपया यहां क्लिक करें ।