एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित गुण होंगे:
एक नोड का राइट सब-ट्री उसके पैरेंट नोड की कुंजी से अधिक कुंजी रखता है।
एक नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की कुंजी से कम कुंजी रखता है।
सभी कुंजी मान विशिष्ट होते हैं।
प्रत्येक नोड में दो से अधिक चाइल्ड नहीं हो सकते।
क्लास विवरण:
Begin class BST निम्नलिखित फंक्शन घोषित करने के लिए: search() = BST में किसी आइटम को खोजने के लिए। temp = root इनिशियलाइज़ करें; while(temp != NULL) गहराई बढ़ाएं if(temp→info == data) डेटा और गहराई प्रिंट करें else if(temp→info > data) temp = temp→l; else temp = temp→r; insert() = ट्री में आइटम डालने के लिए: यदि ट्री खाली है तो डेटा को रूट के रूप में डालें। यदि ट्री खाली नहीं है यदि डेटा < रूट डेटा को लेफ्ट चाइल्ड के रूप में डालें। else डेटा को राइट चाइल्ड के रूप में डालें। del() = ट्री से आइटम हटाने के लिए। casea() = del() से कॉल किया जाता है यदि l = r = null। caseb() = del() से कॉल किया जाता है यदि l != null, r = null। caseb() = del() से कॉल किया जाता है यदि l = null, r != null। casec() = del() से कॉल किया जाता है यदि l != null, r != null। inorder() नोड को इनऑर्डर के रूप में ट्रैवर्स करने के लिए: लेफ्ट – रूट – राइट। preorder() नोड को प्रीऑर्डर के रूप में ट्रैवर्स करने के लिए: रूट – लेफ्ट – राइट। postorder() नोड को पोस्टऑर्डर के रूप में ट्रैवर्स करने के लिए: लेफ्ट – राइट – रूट End
उदाहरण कोड
# include <iostream> # include <cstdlib> using namespace std; struct nod//नोड घोषणा { int info; struct nod *l; struct nod *r; }*r; class BST { public://फंक्शन घोषणा void search(nod *, int); void find(int, nod **, nod **); void insert(nod *, nod *); void del(int); void casea(nod *,nod *); void caseb(nod *,nod *); void casec(nod *,nod *); void preorder(nod *); void inorder(nod *); void postorder(nod *); void show(nod *, int); BST() { r = NULL; } }; void BST::find(int i, nod **par, nod **loc)//आइटम की स्थिति खोजें { nod *ptr, *ptrsave; if (r == NULL) { *loc = NULL; *par = NULL; return; } if (i == r→info) { *loc = r; *par = NULL; return; } if (i < r→info) ptr = r→l; else ptr = r→r; ptrsave = r; while (ptr != NULL) { if (i == ptr→info) { *loc = ptr; *par = ptrsave; return; } ptrsave = ptr; if (i < ptr→info) ptr = ptr→l; else ptr = ptr→r; } *loc = NULL; *par = ptrsave; } void BST::search(nod *root, int data) //खोज रहे हैं { int depth = 0; nod *temp = new nod; temp = root; while(temp != NULL) { depth++; if(temp→info == data) { cout<<"\nData found at depth: "<<depth<<endl; return; } else if(temp→info > data) temp = temp→l; else temp = temp→r; } cout<<"\n Data not found"<<endl; return; } void BST::insert(nod *tree, nod *newnode) { if (r == NULL) { r = new nod; r→info = newnode→info; r→l= NULL; r→r= NULL; cout<<"Root Node is Added"<<endl; return; } if (tree→info == newnode→info) { cout<<"Element already in the tree"<<endl; return; } if (tree→info > newnode→info) { if (tree→l != NULL) { insert(tree→l, newnode); } else { tree→l= newnode; (tree→l)→l = NULL; (tree→l)→r= NULL; cout<<"Node Added To Left"<<endl; return; } } else { if (tree→r != NULL) { insert(tree→r, newnode); } else { tree→r = newnode; (tree→r)→l= NULL; (tree→r)→r = NULL; cout<<"Node Added To Right"<<endl; return; } } } void BST::del(int i) { nod *par, *loc; if (r == NULL) { cout<<"Tree empty"<<endl; return; } find(i, &par, &loc); if (loc == NULL) { cout<<"Item not present in tree"<<endl; return; } if (loc→l == NULL && loc→r == NULL) { casea(par, loc); cout<<"item deleted"<<endl; } if (loc→l!= NULL && loc→r == NULL) { caseb(par, loc); cout<<"item deleted"<<endl; } if (loc→l== NULL && loc→r != NULL) { caseb(par, loc); cout<<"item deleted"<<endl; } if (loc→l != NULL && loc→r != NULL) { casec(par, loc); cout<<"item deleted"<<endl; } free(loc); } void BST::casea(nod *par, nod *loc ) { if (par == NULL) { r= NULL; } else { if (loc == par→l) par→l = NULL; else par→r = NULL; } } void BST::caseb(nod *par, nod *loc) { nod *child; if (loc→l!= NULL) child = loc→l; else child = loc→r; if (par == NULL) { r = child; } else { if (loc == par→l) par→l = child; else par→r = child; } } void BST::casec(nod *par, nod *loc) { nod *ptr, *ptrsave, *suc, *parsuc; ptrsave = loc; ptr = loc→r; while (ptr→l!= NULL) { ptrsave = ptr; ptr = ptr→l; } suc = ptr; parsuc = ptrsave; if (suc→l == NULL && suc→r == NULL) casea(parsuc, suc); else caseb(parsuc, suc); if (par == NULL) { r = suc; } else { if (loc == par→l) par→l = suc; else par→r= suc; } suc→l = loc→l; suc→r= loc→r; } void BST::preorder(nod *ptr) { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { cout<<ptr→info<<" "; preorder(ptr→l); preorder(ptr→r); } } void BST::inorder(nod *ptr)//इनऑर्डर ट्रैवर्सल { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { inorder(ptr→l); cout<<ptr→info<<" "; inorder(ptr→r); } } void BST::postorder(nod *ptr)//पोस्टऑर्डर ट्रैवर्सल { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { postorder(ptr→l); postorder(ptr→r); cout<<ptr→info<<" "; } } void BST::show(nod *ptr, int level)//ट्री प्रिंट करें { int i; if (ptr != NULL) { show(ptr→r, level+1); cout<<endl; if (ptr == r) cout<<"Root→: "; else { for (i = 0;i < level;i++) cout<<" "; } cout<<ptr→info; show(ptr→l, level+1); } } int main() { int c, n,item; BST bst; nod *t; while (1) { cout<<"1.Insert Element "<<endl; cout<<"2.Delete Element "<<endl; cout<<"3.Search Element"<<endl; cout<<"4.Inorder Traversal"<<endl; cout<<"5.Preorder Traversal"<<endl; cout<<"6.Postorder Traversal"<<endl; cout<<"7.Display the tree"<<endl; cout<<"8.Quit"<<endl; cout<<"Enter your choice : "; cin>>c; switch(c) { case 1: t = new nod; cout<<"Enter the number to be inserted : "; cin>>t→info; bst.insert(r, t); break; case 2: if (r == NULL) { cout<<"Tree is empty, nothing to delete"<<endl; continue; } cout<<"Enter the number to be deleted : "; cin>>n; bst.del(n); break; case 3: cout<<"Search:"<<endl; cin>>item; bst.search(r,item); break; case 4: cout<<"Inorder Traversal of BST:"<<endl; bst.inorder(r); cout<<endl; break; case 5: cout<<"Preorder Traversal of BST:"<<endl; bst.preorder(r); cout<<endl; break; case 6: cout<<"Postorder Traversal of BST:"<<endl; bst.postorder(r); cout<<endl; break; case 7: cout<<"Display BST:"<<endl; bst.show(r,1); cout<<endl; break; case 8: exit(1); default: cout<<"Wrong choice"<<endl; } } }
आउटपुट
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 6 Root Node is Added 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 7 Node Added To Right 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 5 Node Added To Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 4 Node Added To Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 7 Data found at depth: 2 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 1 Data not found 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 4 Inorder Traversal of BST: 4 5 6 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 6 Postorder Traversal of BST: 4 5 7 6 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root→: 6 5 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 1 Item not present in tree 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 5 item deleted 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root→: 6 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 8
