C++ में ब्रैकेट के साथ बाइनरी ट्री को स्ट्रिंग में बदलें

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

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

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

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

प्रीऑर्डर ट्रैवर्सल: [4, 1, 8, 3, 9, 2, 5]

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

इनपुट

प्रीऑर्डर: [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()()))।

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

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

उदाहरण

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* insertNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

void ConvertBinaryTreeToString(Node* root, string& str) {
    if (root == NULL)
        return;
    str.push_back(root->data + '0');
    if (!root->left && !root->right)
        return;
    str.push_back('(');
    ConvertBinaryTreeToString(root->left, str);
    str.push_back(')');
    if (root->right) {
        str.push_back('(');
        ConvertBinaryTreeToString(root->right, str);
        str.push_back(')');
    }
}

int main() {
    struct Node* root = insertNode(4);
    root->left = insertNode(1);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->left->left = insertNode(3);
    root->right->left = insertNode(2);
    root->right->right = insertNode(5);
    string binaryTreeString = "";
    ConvertBinaryTreeToString(root, binaryTreeString);
    cout << "ब्रैकेट के साथ बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल स्ट्रिंग है: " << binaryTreeString;
}

आउटपुट

ब्रैकेट के साथ बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल स्ट्रिंग है: 4(1(8(3)))(9(2)(5))