একটি বাইনারী গাছ একটি বিশেষ ধরনের গাছ যেখানে গাছের প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে। এই চাইল্ড নোডগুলি ডান শিশু এবং বাম শিশু হিসাবে পরিচিত।
একটি সাধারণ বাইনারি গাছ হল −
বাইনারী সার্চ ট্রি (BST) একটি বিশেষ ধরনের গাছ যা নিম্নলিখিত নিয়মগুলি অনুসরণ করে -
-
বাম চাইল্ড নোডের মান সবসময়ই প্যারেন্ট নোটের চেয়ে কম হয়
-
প্যারেন্ট নোডের চেয়ে ডান চাইল্ড নোডের মূল্য বেশি।
-
সমস্ত নোড পৃথকভাবে একটি বাইনারি অনুসন্ধান গাছ গঠন করে।
একটি বাইনারি অনুসন্ধান গাছের উদাহরণ (BST) −
সার্চ, ন্যূনতম এবং সর্বোচ্চ সন্ধানের মতো ক্রিয়াকলাপের জটিলতা কমাতে একটি বাইনারি অনুসন্ধান ট্রি তৈরি করা হয়েছে৷
এখানে, আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে এবং আমাদের এই বাইনারি ট্রি (BT) কে রূপান্তর করতে হবে। একটি বাইনারি অনুসন্ধান গাছে (BST) . এই রূপান্তরে, বাইনারি গাছের মূল কাঠামো পরিবর্তন করা উচিত নয়।
কিভাবে একটি BT-এ BST রূপান্তর করা যায় তা বোঝার জন্য একটি উদাহরণ নেওয়া যাক −
ইনপুট৷ - 
আউটপুট - 
একটি বাইনারি ট্রিকে একটি বাইনারি অনুসন্ধান গাছে রূপান্তর তিনটি ধাপ ব্যবহার করে সঞ্চালিত হয়। তারা হল -
ধাপ 1 − একটি বাইনারি ট্রিকে অ্যারে arr[]-এ ট্রাভার্সাল করার জন্য ডেটা সংরক্ষণ করুন .
ধাপ 2 − যেকোন সাজানোর কৌশল ব্যবহার করে অ্যারে arr[] সাজান।
ধাপ 3 − এখন, গাছের অভ্যন্তরীণ ট্রাভার্সাল করুন এবং একটি অ্যারের উপাদানগুলিকে একে একে গাছের নোডগুলিতে অনুলিপি করুন৷
উদাহরণ
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left;
struct node *right;
};
void Inordertraversal(struct node* node, int inorder[], int *index_ptr){
if (node == NULL)
return;
Inordertraversal(node->left, inorder, index_ptr);
inorder[*index_ptr] = node->data;
(*index_ptr)++;
Inordertraversal(node->right, inorder, index_ptr);
}
int countNodes(struct node* root){
if (root == NULL)
return 0;
return countNodes (root->left) +
countNodes (root->right) + 1;
}
int compare (const void * a, const void * b){
return( *(int*)a - *(int*)b );
}
void arrayToBST (int *arr, struct node* root, int *index_ptr){
if (root == NULL)
return;
arrayToBST (arr, root->left, index_ptr);
root->data = arr[*index_ptr];
(*index_ptr)++;
arrayToBST (arr, root->right, index_ptr);
}
struct node* newNode (int data){
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void printInorder (struct node* node){
if (node == NULL)
return;
printInorder (node->left);
printf("%d ", node->data);
printInorder (node->right);
}
int main(){
struct node *root = NULL;
root = newNode(17);
root->left = newNode(14);
root->right = newNode(2);
root->left->left = newNode(11);
root->right->right = newNode(7);
printf("Inorder Traversal of the binary Tree: \n");
printInorder (root);
int n = countNodes(root);
int *arr = new int[n];
int i = 0;
Inordertraversal(root, arr, &i);
qsort(arr, n, sizeof(arr[0]), compare);
i = 0;
arrayToBST (arr, root, &i);
delete [] arr;
printf("\nInorder Traversal of the converted BST: \n");
printInorder (root);
return 0;
} আউটপুট
Inorder Traversal of the binary Tree: 11 14 17 2 7 Inorder Traversal of the converted BST: 2 7 11 14 17
