सी ++ में दिए गए इनऑर्डर और प्रीऑर्डर ट्रैवर्सल से ट्री का निर्माण करें

हमें बाइनरी ट्री के इनऑर्डर और प्रीऑर्डर ट्रैवर्सल दिए गए हैं। लक्ष्य दिए गए ट्रैवर्सल से एक पेड़ का निर्माण करना है।

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

इनऑर्डर (पेड़ की जड़)

• रूट द्वारा इंगित नोड के ट्रैवर्स लेफ्ट सबट्री, कॉल इनऑर्डर (रूट→बाएं)

• रूट पर जाएं

• रूट द्वारा इंगित नोड का ट्रैवर्स राइट सबट्री, कॉल इनऑर्डर (रूट→दाएं)

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

पूर्व-आदेश (पेड़ की जड़)

• रूट पर जाएं
• रूट द्वारा इंगित नोड के बाएं उपट्री को पार करें, क्रम में कॉल करें (रूट→बाएं)
• रूट द्वारा इंगित नोड के दाएं उपट्री को पार करें, इनऑर्डर (रूट→दाएं) को कॉल करें

नीचे के पेड़ का इनऑर्डर और प्रीऑर्डर ट्रैवर्सल दिया गया है -

इनऑर्डर

2-3-4-5-6-8-10

प्रीआर्डर

4-3-2-5-8-6-10

अब हम दिए गए अग्रिम-आदेश और इन-ऑर्डर ट्रैवर्सल के लिए उपरोक्त पेड़ को फिर से बनाएंगे।

इनऑर्डर

2-3-4-5-6-8-10

प्रीआर्डर

5-3-2-4-8-6-10

• जैसा कि हम जानते हैं कि प्रीऑर्डर पहले रूट नोड पर जाता है, फिर पहला मान हमेशा पेड़ की जड़ का प्रतिनिधित्व करता है। उपरोक्त क्रम से 5 पेड़ की जड़ है।

प्रीआर्डर

5 -3-2-4-8-6-10

• उपरोक्त इनऑर्डर ट्रैवर्सल से, हम जानते हैं कि एक नोड के बाएं सबट्री को उसके दाएं सबट्री के बाद उसके पहले ट्रैवर्स किया जाता है। इसलिए, क्रम में 5 के बाईं ओर के सभी मान इसके बाएँ सबट्री के हैं और दाईं ओर के सभी मान इसके राइट सबट्री के हैं।

इनऑर्डर

2-3-4 ← 5 → 6-8-10

• अब बाएं सबट्री के लिए ऊपर जैसा ही करें।

बाएं सबट्री का प्रीऑर्डर ट्रैवर्सल 3 -2-4 है। तो 3 मूल बन जाता है।

इनऑर्डर ट्रैवर्सल को आगे 2 ← 3 → 4

• अब सही सबट्री के लिए ऊपर जैसा ही करें।

दाएं सबट्री का प्रीऑर्डर ट्रैवर्सल 8 -6-10 है। तो 8 जड़ बन जाता है।

इनऑर्डर ट्रैवर्सल को आगे 6 ← 8 → 10

तो, इस तरह हमने दिए गए प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से मूल पेड़ का निर्माण किया।