इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो बाइनरी सर्च ट्री में उन सभी जोड़ों को ढूंढता है जिनका योग दी गई संख्या के बराबर है।
हम जोड़े ढूंढने के लिए ट्री के मानों को दो अलग-अलग सूचियों में संग्रहीत करने जा रहे हैं। आइए प्रॉब्लम को हल करने के चरण देखें।
बाइनरी ट्री के लिए एक स्ट्रक्चर नोड बनाएं।
बाइनरी सर्च ट्री में एक नया नोड डालने के लिए एक फंक्शन लिखें।
याद रखें, बाइनरी सर्च ट्री में रूट से छोटे सभी तत्व बाएं होते हैं, और दाएं बड़े होते हैं।
ट्री के बाएं और दाएं नोड्स को संग्रहीत करने के लिए दो खाली सूचियां इनिशियलाइज़ करें।
बाइनरी सर्च ट्री पर तब तक पुनरावृति करें जब तक बाएं या दाएं नोड्स 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;
right_side_nodes.pop_back();
left_side_nodes.pop_back();
current_left = left_side_node->right;
current_right = right_side_node->left;
}
}
}
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, 50);
}
आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम मिलेगा।
19 31 20 30
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें टिप्पणी अनुभाग में उल्लेख करें।
