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

C++ में दो बाइनरी ट्री को मर्ज करना


मान लीजिए हमारे पास दो बाइनरी ट्री हैं और जब हम एक को दूसरे पर ओवरलैप करते हैं, तो कुछ नोड्स ओवरलैप होते हैं जबकि अन्य नहीं। हमें इन्हें एक नए बाइनरी ट्री में मर्ज करना है। मर्ज का नियम यह है कि यदि दो नोड्स ओवरलैप होते हैं, तो उनके मानों को जोड़कर मर्ज किए गए नोड का नया मान बनाया जाता है। अन्यथा, गैर-खाली नोड को नए ट्री के नोड के रूप में उपयोग किया जाता है।

समस्या विवरण

यदि ट्री इस प्रकार हैं -

C++ में दो बाइनरी ट्री को मर्ज करना

तो आउटपुट होगा -

C++ में दो बाइनरी ट्री को मर्ज करना

एल्गोरिदम

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे -

  • मेथड है mergeTrees()। यह दो ट्री नोड्स n1 और n2 लेता है।

  • यदि n1 खाली है और n2 गैर-खाली है, तो n2 लौटाएं। अन्यथा जब n2 खाली है और n1 गैर-खाली है, तो n1 लौटाएं। जब दोनों null हों, तो null लौटाएं।

  • n1 का मान := n1 का मान + n2 का मान

  • n1 का बायां := mergeTrees(n1 का बायां, n2 का बायां)

  • n1 का दायां := mergeTrees(n1 का दायां, n2 का दायां)

  • n1 लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

#include <bits/stdc++.h> 
using namespace std; 

class TreeNode { 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data) { 
        val = data; 
        left = right = NULL; 
    } 
}; 

void insert(TreeNode **root, int val) { 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()) { 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left) { 
            temp->left = new TreeNode(val); 
            return; 
        } else { 
            q.push(temp->left); 
        } 
        if(!temp->right) { 
            temp->right = new TreeNode(val); 
            return; 
        } else { 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v) { 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i < v.size(); i++) { 
        insert(&root, v[i]); 
    } 
    return root; 
} 

void tree_level_trav(TreeNode* root) { 
    if (root == NULL) return; 
    cout << "["; 
    queue<TreeNode *> q; 
    TreeNode *curr; 
    q.push(root); 
    q.push(NULL); 
    while (q.size() > 1) { 
        curr = q.front(); 
        q.pop(); 
        if (curr == NULL) { 
            q.push(NULL); 
        } else { 
            if(curr->left) q.push(curr->left); 
            if(curr->right) q.push(curr->right); 
            if(curr->val == 0) { 
                cout << "null" << ", "; 
            } else { 
                cout << curr->val << ", "; 
            } 
        } 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    TreeNode* mergeTrees(TreeNode* n1, TreeNode* n2) { 
        if(!n1 && n2) { 
            return n2; 
        } else if(!n2 && n1) return n1; 
        else if(!n1 && !n2) return NULL; 
        n1->val += n2->val; 
        n1->left = mergeTrees(n1->left, n2->left); 
        n1->right = mergeTrees(n1->right, n2->right); 
        return n1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v1 = {1, 3, 2, 5}; 
    vector<int> v2 = {2, 1, 3, NULL, 4, NULL, 7}; 
    TreeNode *root1 = make_tree(v1); 
    TreeNode *root2 = make_tree(v2); 
    root1 = ob.mergeTrees(root1, root2); 
    tree_level_trav(root1); 
}

इनपुट

[1,3,2,5] [2,1,3,null,4,null,7]

आउटपुट

[3, 4, 5, 5, 4, null, 7, ]

  1. C++ में अद्वितीय बाइनरी सर्च ट्री C++ में अद्वितीय बाइनरी सर्च ट्री

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री की गिनती करनी है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो आउटपुट 5 होगा, क्योंकि ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:आ

  1. C++ में अद्वितीय बाइनरी सर्च ट्री II C++ में अद्वितीय बाइनरी सर्च ट्री II

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री को उत्पन्न करना है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:generate() नामक एक पुन

  1. C++ में दो बाइनरी ट्री में पहला गैर-मेल खाने वाला पत्ता ज्ञात करें C++ में दो बाइनरी ट्री में पहला गैर-मेल खाने वाला पत्ता ज्ञात करें

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें दोनों ट्री का पहला पत्ता ढूंढना है, जो मेल नहीं खाता। यदि कोई गैर-मेल खाने वाले पत्ते नहीं हैं, तो कुछ भी प्रदर्शित न करें। यदि ये दो ट्री हैं, तो पहला गैर-मेल खाने वाले पत्ते 11 और 15 हैं। यहां हम स्टैक का उपयोग करके दोनों ट्री के पुनरावृत्त प्रीऑर्डर ट