एक बाइनरी ट्री एक विशेष प्रकार का पेड़ है जिसमें पेड़ के प्रत्येक नोड में अधिकतम दो बच्चे नोड हो सकते हैं। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के रूप में जाना जाता है।
एक साधारण बाइनरी ट्री है -
बाइनरी सर्च ट्री (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