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