এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম লিখতে যাচ্ছি যেটি সমস্ত জোড়া খুঁজে বের করে যার যোগফল বাইনারি সার্চ ট্রিতে প্রদত্ত সংখ্যার সমান।
আমরা জোড়া খুঁজে পেতে দুটি ভিন্ন তালিকায় গাছের মূল্য সংরক্ষণ করতে যাচ্ছি। আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
একটি বাইনারি গাছের জন্য একটি স্ট্রাকট নোড তৈরি করুন।
-
বাইনারি সার্চ ট্রিতে একটি নতুন নোড সন্নিবেশ করার জন্য একটি ফাংশন লিখুন।
-
মনে রাখবেন, বাইনারি সার্চ ট্রিতে মূলের চেয়ে কম উপাদানগুলি ছোট এবং ডানগুলি বড়৷
-
-
গাছের বাম এবং ডান নোডগুলি সংরক্ষণ করতে দুটি খালি তালিকা শুরু করুন৷
-
বাইনারি সার্চ ট্রিতে পুনরাবৃত্তি করুন যতক্ষণ না বাম বা ডান নোডগুলি NULL হয় বা উভয় তালিকাই খালি না হয়৷
-
বাম নোড তালিকায় সমস্ত উপাদান সংরক্ষণ করার জন্য একটি লুপ লিখুন।
-
সঠিক নোড তালিকায় সমস্ত উপাদান সংরক্ষণ করার জন্য একটি লুপ লিখুন।
-
প্রতিটি তালিকা থেকে শেষ নোডগুলি পান৷
-
দুটি মান পরীক্ষা করুন।
-
যদি বাম দিকের নোডের মান ডান পাশের নোডের মানের থেকে বেশি বা সমান হয়, তাহলে লুপটি ভেঙে দিন।
-
যদি দুটি মানের যোগফল প্রদত্ত সংখ্যার সমান হয়, তাহলে তালিকাগুলি থেকে মুদ্রণ করুন এবং মুছুন
-
যদি দুটি মানের যোগফল প্রদত্ত সংখ্যার থেকে কম হয়, তাহলে বাম তালিকা থেকে শেষ নোডটি মুছে দিন এবং নোডের ডানদিকে যান৷
-
যদি দুটি মানের যোগফল প্রদত্ত সংখ্যার চেয়ে বড় হয়, তাহলে ডান তালিকা থেকে শেষ নোডটি মুছে দিন এবং নোডের বাম দিকে যান৷
-
-
উদাহরণ
আসুন কোডটি দেখি।
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right, *root;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
root = 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);
}t, *root;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
root = 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 tar) {
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 < tar) {
left_side_nodes.pop_back();
current_left = left_side_node->right;
}
else if (left_side_value + right_side_value > tar) {
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
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
