একটি বাইনারি গাছ দেওয়া. কাজটি হল পাতার নোডগুলিকে জোড়ায় জোড়ায় অদলবদল করা, উদাহরণস্বরূপ −
ইনপুট -
আউটপুট -
আমরা দুটি পয়েন্টারের ট্র্যাক রাখব যা দুটি সংলগ্ন লিফ নোডকে নির্দেশ করে এবং প্রদত্ত সমস্যায় তাদের মানগুলি অদলবদল করে৷
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমরা গাছটি অতিক্রম করি, পাতার নোডগুলি খুঁজে পাই এবং বর্তমান গণনা পরীক্ষা করার জন্য আমাদের কাউন্টারের ট্র্যাক রাখি। প্রধান কৌশল হল যে আমাদের কাউন্টার বিজোড়, তাই আমাদের প্রথম পয়েন্টার এখন সেই নোডের দিকে নির্দেশ করে। যখন আমাদের কাউন্টার সমান হয়ে যায়, তখন আমরা ডেটা অদলবদল করি এবং তাই আমাদের লিফ নোডগুলি অদলবদল করা হয়৷
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
struct Node{ // structure of our tree node
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // the swapping utility function
Node * temp = *a;
*a = *b;
*b = temp;
}
/********Pointers for leaf nodes for swapping********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//recursive function for
//Swapping leaf nodes
if (!(*root)) // if root is null we return
return;
if(!(*root)->left &&!(*root)->right){ // condition for leaf node
secondleaf = root; // now we firstly make our second pointer point to this node
count++; // we also increment the count
if (count%2 == 0) // now if our count is even that means we have a pair so we can swap them
Swap(firstleaf, secondleaf);
else // if count is odd so that means we only got first node yet
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // function for initializing new node
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // inorder traversal function
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* Creating binary tree*/
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
int count = 0; // out counter for keeping track of leaf nodes
SwapTheLeafNodes(&root, count); // swapping the nodes
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
} আউটপুট
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
উপরের কোডের ব্যাখ্যা
উপরের পদ্ধতিতে, আমরা কেবল দুটি পয়েন্টার তৈরি করছি যা আমাদের লিফ নোডগুলির উপর নজর রাখবে। যখন আমরা একটি পাতার নোডের সম্মুখীন হই তখন আমরা গাছটি অতিক্রম করি। আমরা প্রথমে আমাদের দ্বিতীয় পয়েন্টারটি সেই নোডের দিকে নির্দেশ করি এখন আমরা একটি কাউন্ট ভেরিয়েবল বৃদ্ধি করি যদি আমাদের গণনা জোড় হয়, তাই আমরা নোডগুলি অদলবদল করি এবং গণনাটি যদি বিজোড় হয়, তার মানে আমরা শুধুমাত্র আমাদের জোড়ার প্রথম উপাদানটি খুঁজে পেয়েছি, তাই আমরা সেই মানটিকে প্রথম পয়েন্টারে সংরক্ষণ করুন এবং আমাদের ফাংশন এভাবেই কাজ করে।
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি বাইনারি গাছে পেয়ারওয়াইজ সোয়াপ লিফ নোডের সমস্যার সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
