Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

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

इनऑर्डर (ट्री रूट):

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

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

प्रीऑर्डर (ट्री रूट):

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

नीचे दिए गए ट्री के इनऑर्डर और प्रीऑर्डर ट्रैवर्सल दिए गए हैं:

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

इनऑर्डर

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

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

  • अब बाएं उपट्री के लिए वही करें।

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

इनऑर्डर ट्रैवर्सल आगे 2 ← 3 → 4 में विभाजित होता है।

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

  • अब दाएं उपट्री के लिए वही करें।

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

इनऑर्डर ट्रैवर्सल आगे 6 ← 8 → 10 में विभाजित होता है।

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

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


  1. पायथन में प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल से बाइनरी ट्री निर्माण पायथन में प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल से बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास दो ट्रैवर्सल अनुक्रम प्रीऑर्डर और पोस्टऑर्डर हैं, हमें इन दो अनुक्रमों से बाइनरी ट्री उत्पन्न करना है। इसलिए यदि अनुक्रम [1,2,4,5,3,6,7], [4,5,2,6,7,3,1] हैं, तो आउटपुट होगा इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - ans := pre[0] मान लेकर एक ट्री नोड बनाएं, stack := खा

  1. पायथन में इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं पायथन में इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं

    मान लीजिए हमारे पास एक बाइनरी ट्री का इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से ट्री उत्पन्न करना है। इसलिए यदि पोस्टऑर्डर और इनऑर्डर अनुक्रम [9,15,7,20,3] और [9,3,15,20,7] हैं, तो ट्री होगा - आइए चरण देखते हैं - मान लीजिए मेथड को buildTree कहा जाता है जिसमें प्रीऑर्डर और इन

  1. पायथन में प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं पायथन में प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं

    मान लीजिए हमारे पास एक बाइनरी ट्री का इनऑर्डर और प्रीऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से ट्री उत्पन्न करना है। इसलिए यदि प्रीऑर्डर और इनऑर्डर अनुक्रम [3,9,20,15,7] और [9,3,15,20,7] हैं, तो ट्री होगा - आइए चरण देखते हैं - मान लीजिए मेथड को buildTree कहा जाता है जिसमें प्रीऑर्डर और इनऑर