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

C++ में BST में दिए गए योग वाला जोड़ा खोजें


इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो बाइनरी सर्च ट्री में उस जोड़े को ढूंढता है जिसका योग दी गई संख्या के बराबर है।

हम जोड़े ढूंढने के लिए ट्री के मानों को दो अलग-अलग सूचियों में संग्रहीत करने जा रहे हैं। आइए प्रॉब्लम को हल करने के चरण देखें।

  • बाइनरी ट्री के लिए एक स्ट्रक्चर नोड बनाएं।

  • बाइनरी सर्च ट्री में एक नया नोड डालने के लिए एक फंक्शन लिखें।

    • याद रखें, बाइनरी सर्च ट्री में रूट से छोटे सभी तत्व बाएं होते हैं, और दाएं बड़े होते हैं।

  • ट्री के बाएं और दाएं नोड्स को संग्रहीत करने के लिए दो खाली सूचियां इनिशियलाइज़ करें।

  • बाइनरी सर्च ट्री पर तब तक पुनरावृति करें जब तक बाएं या दाएं नोड्स NULL न हों या दोनों सूचियां खाली न हों।

    • बाएं नोड्स सूची में सभी तत्वों को संग्रहीत करने के लिए एक लूप लिखें।

    • दाएं नोड्स सूची में सभी तत्वों को संग्रहीत करने के लिए एक लूप लिखें।

    • प्रत्येक सूची से अंतिम नोड्स प्राप्त करें।

    • दोनों मानों की जांच करें।

      • यदि बाएं तरफ का नोड मान दाएं तरफ के नोड मान से बड़ा या बराबर है, तो लूप तोड़ें।

      • यदि दो मानों का योग दी गई संख्या के बराबर है, तो प्रिंट करें और लूप तोड़ें।

      • यदि दो मानों का योग दी गई संख्या से कम है, तो बाएं सूची से अंतिम नोड को हटाएं और नोड के दाएं जाएं।

      • यदि दो मानों का योग दी गई संख्या से अधिक है, तो दाएं सूची से अंतिम नोड को हटाएं और नोड के बाएं जाएं।

उदाहरण

आइए कोड देखें।

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

struct Node {
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

Node* insertNewNode(Node *root, int data) {
    if (root == NULL) {
        root = new Node(data);
        return root;
    }
    if (root->data < data) {
        root->right = insertNewNode(root->right, data);
    } else if (root->data > data) {
        root->left = insertNewNode(root->left, data);
    }
    return root;
}

void findThePairs(Node *node, int target) {
    vector<Node*> left_side_nodes;
    vector<Node*> right_side_nodes;
    Node *current_left = node;
    Node *current_right = node;
    while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
        while (current_left != NULL) {
            left_side_nodes.push_back(current_left);
            current_left = current_left->left;
        }
        while (current_right != NULL) {
            right_side_nodes.push_back(current_right);
            current_right = current_right->right;
        }
        Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
        Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
        int left_side_value = left_side_node->data;
        int right_side_value = right_side_node->data;
        if (left_side_value >= right_side_value) {
            break;
        }
        if (left_side_value + right_side_value < target) {
            left_side_nodes.pop_back();
            current_left = left_side_node->right;
        } else if (left_side_value + right_side_value > target) {
            right_side_nodes.pop_back();
            current_right = right_side_node->left;
        } else {
            cout << left_side_node->data << " " << right_side_node->data << endl;
            break;
        }
    }
}

int main() {
    Node *root = NULL;
    root = insertNewNode(root, 25);
    root = insertNewNode(root, 20);
    root = insertNewNode(root, 30);
    root = insertNewNode(root, 15);
    root = insertNewNode(root, 21);
    root = insertNewNode(root, 19);
    root = insertNewNode(root, 31);
    findThePairs(root, 36);
}

आउटपुट

यदि आप उपरोक्त प्रोग्राम को निष्पादित करते हैं, तो आपको निम्न परिणाम मिलेगा।

15 21

निष्कर्ष

यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें टिप्पणी अनुभाग में उल्लेख करें।


  1. C++ में जांचें कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है C++ में जांचें कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है

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

  1. संतुलित BST में दिए गए योग वाली जोड़ी खोजें C++ में संतुलित BST में दिए गए योग वाली जोड़ी खोजें C++ में

    मान लीजिए हमारे पास एक संतुलित बाइनरी सर्च ट्री (BST) और एक लक्ष्य योग है, हमें एक ऐसी विधि परिभाषित करनी है जो जांचे कि क्या इसमें कोई ऐसी जोड़ी मौजूद है जिसका योग लक्ष्य योग के बराबर हो। ध्यान रखें कि बाइनरी सर्च ट्री अपरिवर्तनीय (immutable) है। उदाहरण के लिए, यदि इनपुट इस तरह का है: तो आउटपुट हो

  1. Java में बैलेंस्ड BST में दिए गए योग के साथ एक जोड़ी खोजें Java में बैलेंस्ड BST में दिए गए योग के साथ एक जोड़ी खोजें

    अवधारणाएक दिए गए बैलेंस्ड बाइनरी सर्च ट्री और एक टारगेट योग के संबंध में, हम एक फ़ंक्शन लिखते हैं जो true वापस करता है यदि कोई जोड़ी है जिसका योग टारगेट योग के बराबर है, अन्यथा false वापस करता है। इस मामले में, अपेक्षित समय जटिलता O(n) है और केवल O(log n) अतिरिक्त स्पेस लागू किया जा सकता है। यहां, ब