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

C++ में बाइनरी ट्री में दूसरा न्यूनतम नोड


मान लीजिए एक गैर-खाली विशेष बाइनरी ट्री है जिसमें कुछ गैर-ऋणात्मक मान हैं, यहां इस ट्री में प्रत्येक नोड के ठीक दो या शून्य बच्चे हैं। यदि नोड के दो बच्चे हैं, तो इस नोड का मान उसके दो बच्चों में से छोटा मान है। दूसरे शब्दों में, हम कह सकते हैं कि [root.val = min(root.left.val, root.right.val)]। यदि हमारे पास ऐसा बाइनरी ट्री है, तो हमें पूरे ट्री में सभी नोड्स के मानों के समुच्चय में दूसरा न्यूनतम मान ढूंढना है। यदि ऐसा कोई तत्व नहीं है, तो -1 वापस करें।

इसलिए, यदि इनपुट जैसा है:

C++ में बाइनरी ट्री में दूसरा न्यूनतम नोड

तो आउटपुट 5 होगा। सबसे छोटा मान 2 है, दूसरा सबसे छोटा मान 5 है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • एक फ़ंक्शन TraverseNodes() परिभाषित करें, जो node, min, nextMin लेगा,
    • यदि node null है, तो वापस लौटें
    • यदि node का मान > min, तो:
      • यदि nextMin == -1 या node का मान < nextMin, तो:
        • nextMin := node का मान
    • TraverseNodes(node का बायां, min, nextMin)
    • TraverseNodes(node का दायां, min, nextMin)
  • मुख्य विधि से निम्नलिखित करें:
    • min := root का मान यदि root null नहीं है, अन्यथा -1
    • nextMin := -1
    • TraverseNodes(root, min, nextMin)
    • nextMin वापस करें

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

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = NULL; 
        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){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        }else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            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; 
} 
class Solution { 
public: 
    int findSecondMinimumValue(TreeNode* root) { 
        int min = (root && root->val != 0) ? root->val : -1; 
        int nextMin = -1; 
        TraverseNodes(root, min, nextMin); 
        return nextMin; 
    } 
    void TraverseNodes(TreeNode* node, int min, int& nextMin) { 
        if (!node || node->val == 0) { 
            return; 
        } 
        if (node->val > min) { 
            if (nextMin == -1 || node->val < nextMin) { 
                nextMin = node->val; 
            } 
        } 
        TraverseNodes(node->left, min, nextMin); 
        TraverseNodes(node->right, min, nextMin); 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<int> v = {2,2,5,NULL,NULL,5,7}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.findSecondMinimumValue(root)); 
}

इनपुट

{2,2,5,NULL,NULL,5,7}

आउटपुट

5
  1. C++ में बाइनरी ट्री में नोड का प्रीऑर्डर प्रीडिसेसर C++ में बाइनरी ट्री में नोड का प्रीऑर्डर प्रीडिसेसर

    इस समस्या में, हमें एक बाइनरी ट्री और एक नोड मान दिया गया है। हमारा कार्य नोड का प्रीऑर्डर प्रीडिसेसर प्रिंट करना है।बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक रूट नोड में अधिकतम 2 चाइल्ड नोड्स हो सकते हैं।प्रीऑर्डर ट्रैवर्सल ट्री के नोड्स को पार करने का एक तरीका है। इसमें हम पहले र

  1. C++ में बाइनरी ट्री में नोड का प्रीऑर्डर सक्सेसर C++ में बाइनरी ट्री में नोड का प्रीऑर्डर सक्सेसर

    इस समस्या में, हमें एक बाइनरी ट्री और एक नोड मान दिया गया है। हमारा कार्य नोड का प्रीऑर्डर सक्सेसर प्रिंट करना है।बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक रूट नोड में अधिकतम 2 चाइल्ड नोड्स हो सकते हैं।प्रीऑर्डर ट्रैवर्सल ट्री के नोड्स को पार करने का एक तरीका है। इसमें हम पहले रूट नोड क

  1. C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें बाइनरी सर्च ट्री में न्यूनतम तत्व ढूंढना है। इसलिए यदि BST नीचे की तरह है: न्यूनतम तत्व 1 होगा। जैसा कि हम जानते हैं कि बायां उपट्री हमेशा छोटे तत्वों को धारण करता है। इसलिए यदि हम बाएं उपट्री के माध्यम से तब तक ट्रैवर्स करते हैं जब तक बायां NULL नही