सी ++ में ब्रैकेट के साथ स्ट्रिंग करने के लिए बाइनरी पेड़

इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम एक प्रोग्राम बनाना है जो एक बाइनरी ट्री को C++ में ब्रैकेट के साथ स्ट्रिंग में बदल देगा।

बाइनरी ट्री के मान पूर्णांक हैं और इसे प्रोग्राम को प्रीऑर्डर ट्रैवर्सिंग तरीके से फीड किया जाएगा। स्ट्रिंग में केवल पूर्णांक और कोष्ठक () होना चाहिए, इसे भी अनुकूलित किया जाना चाहिए यानी सभी खाली जोड़े को हटा दिया जाना चाहिए।

बाइनरी ट्री एक पेड़ है जिसकी एक विशेष शर्त है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।

बाइनरी ट्री का उदाहरण -

अग्रिम-आदेश ट्रैवर्सल :[4, 1, 8, 3, 9, 2, 5]

समस्या को समझने के लिए एक उदाहरण लेते हैं -

इनपुट

आउटपुट

स्पष्टीकरण

रूट -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8( 3)())())(9) -> 4(1(8(3)())())(9(2)(5))

सभी खाली कोष्ठक हटा रहा है,

4(1(8(3)))(9(2)(5))

अब, समस्या को हल करते हैं, हम बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल करेंगे और जहां भी आवश्यक होगा हम कोष्ठक लगाएंगे। साथ ही, हमें अतिरिक्त जोड़ी ब्रेसिज़ को हटाना होगा। इसके लिए, हम एक फ़ंक्शन के लिए पुनरावर्ती कॉलिंग का उपयोग करेंगे जो कोष्ठक लगाएगा।

हम एक नोड प्रिंट करेंगे और नोड के दोनों बच्चे के लिए रिकर्सिव फ़ंक्शन को वाक्यों के साथ कॉल करेंगे जब तक कि नोड यानी लीफ नोड के लिए कोई बच्चा नहीं बचा है।

नोड के चाइल्ड नोड्स के लिए फ़ंक्शन को कॉल करते समय हम इन 4 मामलों में से एक का सामना करेंगे -

केस1 - जब नोड में दोनों चाइल्ड नोड मौजूद हों। हम दोनों बच्चे के लिए कोष्ठक रखेंगे और उनके मूल्यों को कोष्ठक के अंदर रखेंगे और यदि कोई हो तो उनके बच्चे के नोड्स को कॉल करेंगे।

उदाहरण - रूट नोड के लिए ऊपर के उदाहरण से, 4 जहां दोनों चाइल्ड नोड मौजूद हैं, 4(1)(9)।

केस 2 - जब नोड में केवल लेफ्ट-चाइल्ड हो। हम बाएँ बच्चे को कोष्ठक में रखेंगे, क्योंकि कोई दायाँ बच्चा मौजूद नहीं है तो उसका कोष्ठक हटा दिया जाएगा। और केवल बाएं बच्चे के उप-वृक्षों को कहा जाता है यदि कोई हो।

उदाहरण - ऊपर के उदाहरण से मान 1 वाले नोड के लिए जहां केवल बायां चाइल्ड नोड मौजूद है, 4(1(8()()))(9)।

केस 3 - जब नोड में केवल राइट-चाइल्ड हो। हम बाएं बच्चे के लिए एक खाली ब्रैकेट रखेंगे। और सही बच्चे का मूल्य रखा जाएगा और उसके उप-वृक्षों को यदि कोई हो तो कहा जाएगा।

केस 4 - जब नोड का कोई बच्चा नहीं है (लीफ नोड)। हम कोई कोष्ठक और केवल मान नहीं रखेंगे।

उदाहरण - ऊपर के उदाहरण से 5 मान वाले नोड्स के लिए जहां कोई बच्चा मौजूद नहीं है, 4(1(8(3)))(9(2)(5()()))।

बाइनरी ट्री को ब्रैकेट वाले स्ट्रिंग्स में बदलने का प्रोग्राम

// बाइनरी ट्री को ब्रैकेट वाले स्ट्रिंग में बदलने का प्रोग्राम

उदाहरण

#शामिल नाम स्थान का उपयोग कर; स्ट्रक्चर नोड {इंट डेटा; नोड * लेफ्ट, * राइट;}; नोड * इन्सर्ट नोड (इंट डेटा) {नोड * नोड =(नोड *) मॉलोक (आकार (नोड)); नोड-> डेटा =डेटा; नोड-> लेफ्ट =नोड-> राइट =न्यूल; वापसी (नोड);} शून्य ConveryBinaryTreeToString (नोड * रूट, स्ट्रिंग और स्ट्र) {अगर (रूट ==न्यूल) वापसी; str.push_back (रूट-> डेटा + '0'); if (!root->left &&!root->right) return; str.push_back('('); ConveryBinaryTreeToString(root->left, str); str.push_back(')'); अगर (रूट-> राइट) {str.push_back ('('); ConveryBinaryTreeToString (रूट-> राइट, स्ट्र); str.push_back (')'); }}इंट मेन () {स्ट्रक्चर नोड* रूट =इन्सर्टनोड(4); रूट-> लेफ्ट =इन्सर्टनोड (1); रूट-> राइट =इन्सर्ट नोड (9); रूट-> लेफ्ट-> लेफ्ट =इन्सर्टनोड (8); रूट-> लेफ्ट-> लेफ्ट-> लेफ्ट =इन्सर्टनोड (3); रूट-> राइट-> लेफ्ट =इन्सर्ट नोड (2); रूट-> राइट-> राइट =इन्सर्टनोड (5); स्ट्रिंग बाइनरीट्रीस्ट्रिंग =""; ConveryBinaryTreeToString (रूट, बाइनरी ट्रीस्ट्रिंग); cout<<"कोष्ठक के साथ बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल के साथ स्ट्रिंग है:"< 
आउटपुट
 
कोष्ठक के साथ बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल के साथ स्ट्रिंग है:4(1(8(3)))(9(2)(5))