इस प्रोग्राम में हमें बाइनरी सर्च ट्री में खोज अनुक्रम के अस्तित्व को खोजने के लिए बाइनरी सर्च लागू करने की आवश्यकता है। बाइनरी सर्च की सबसे खराब स्थिति की समय जटिलता O(n) है लेकिन औसत स्थिति में O(log n)।
एल्गोरिदम
शुरुआत दिए गए अनसॉर्टेड डेटा सरणी के लिए बाइनरी सर्च ट्री बनाएं डेटा को एक-एक करके ट्री में डालकर। BST में खोजे जाने वाले डेटा का इनपुट लें। अब रूट नोड से शुरू करके, डेटा की तुलना नोड के डेटा भाग से करें। यदि डेटा < temp->d, तो टेम्प पॉइंटर को बाएं चाइल्ड पर ले जाएं। यदि डेटा > temp->d तो टेम्प पॉइंटर को दाएं चाइल्ड पर ले जाएं। यदि डेटा = temp->d तो ट्री की गहराई प्रिंट करें जहां यह मिला और मेन पर लौटें। अन्यथा आइटम नहीं मिला प्रिंट करें। अंत
उदाहरण कोड
#include<iostream> using namespace std; struct node { int d; node *left; node *right; }; node* CreateNode(int d) { node *newnode = new node; newnode->d = d; newnode->left = NULL; newnode->right = NULL; return newnode; } node* InsertIntoTree(node* root, int d) { node *temp = CreateNode(d); node *t = new node; t = root; if(root == NULL) root = temp; else { while(t != NULL) { if(t->d < d) { if(t->right == NULL) { t->right = temp; break; } t = t->right; } else if(t->d > d) { if(t->left == NULL) { t->left = temp; break; } t = t->left; } } } return root; } void Search(node *root, int d) { int depth = 0; node *temp = new node; temp = root; while(temp != NULL) { depth++; if(temp->d == d) { cout<<"\nआइटम गहराई पर मिला: "<<depth; return; } else if(temp->d > d) temp = temp->left; else temp = temp->right; } cout<<"\n आइटम नहीं मिला"; return; } int main() { char ch; int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76}; node *root = new node; root = NULL; for (i = 0; i < 10; i++) root = InsertIntoTree(root, a[i]); up: cout<<"\nखोजे जाने वाले एलिमेंट को दर्ज करें: "; cin>>n; Search(root, n); cout<<"\n\n\tक्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)?"; cin>>ch; if(c == 'y' || c == 'Y') goto up; return 0; } आउटपुट
खोजे जाने वाले एलिमेंट को दर्ज करें: 26 आइटम गहराई 7 पर मिला क्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)? खोजे जाने वाले एलिमेंट को दर्ज करें: 1 आइटम नहीं मिला क्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)?
