बाइनरी सर्च ट्री वे बाइनरी ट्री हैं जिनमें कुछ गुण होते हैं। ये गुण निम्न हैं:
- प्रत्येक बाइनरी सर्च ट्री एक बाइनरी ट्री है
- प्रत्येक लेफ्ट चाइल्ड रूट से कम मान रखेगा
- प्रत्येक राइट चाइल्ड रूट से अधिक मान रखेगा
- आदर्श बाइनरी सर्च ट्री समान मान को दो बार नहीं रखेगा।
मान लीजिए हमारे पास ऐसा एक ट्री है:
यह ट्री एक बाइनरी सर्च ट्री है। यह उल्लिखित सभी गुणों का पालन करता है। यदि हम तत्वों को इनऑर्डर ट्रैवर्सल मोड में ट्रैवर्स करते हैं, तो हमें 5, 8, 10, 15, 16, 20, 23 मिल सकते हैं। आइए एक कोड देखें ताकि समझ सकें कि हम इसे C++ कोड में कैसे लागू कर सकते हैं।
उदाहरण
#include<iostream> using namespace std; class node{ public: int h_left, h_right, bf, value; node *left, *right; }; class tree{ private: node *get_node(int key); public: node *root; tree(){ root = NULL; //शुरुआत में रूट को NULL सेट करें } void inorder_traversal(node *r); node *insert_node(node *root, int key); }; node *tree::get_node(int key){ node *new_node; new_node = new node; //डायनामिक रूप से एक नया नोड बनाएं new_node->h_left = 0; new_node->h_right = 0; new_node->bf = 0; new_node->value = key; //दिए गए की से मान स्टोर करें new_node->left = NULL; new_node->right = NULL; return new_node; } void tree::inorder_traversal(node *r){ if(r != NULL){ //जब रूट मौजूद है, लेफ्ट - रूट - राइट विजिट करें inorder_traversal(r->left); cout << r->value << " "; inorder_traversal(r->right); } } node *tree::insert_node(node *root, int key){ if(root == NULL){ return (get_node(key)); //जब ट्री खाली है, रूट के रूप में एक नोड बनाएं } if(key < root->value){ //जब की रूट मान से छोटी है, बाएं जाएं root->left = insert_node(root->left, key); }else if(key > root->value){ //जब की रूट मान से बड़ी है, दाएं जाएं root->right = insert_node(root->right, key); } return root; //जब की पहले से मौजूद है, इसे फिर से इन्सर्ट न करें } main(){ node *root; tree my_tree; //ट्री में कुछ कीज़ इन्सर्ट करें। my_tree.root = my_tree.insert_node(my_tree.root, 10); my_tree.root = my_tree.insert_node(my_tree.root, 5); my_tree.root = my_tree.insert_node(my_tree.root, 16); my_tree.root = my_tree.insert_node(my_tree.root, 20); my_tree.root = my_tree.insert_node(my_tree.root, 15); my_tree.root = my_tree.insert_node(my_tree.root, 8); my_tree.root = my_tree.insert_node(my_tree.root, 23); cout << "In-Order Traversal: "; my_tree.inorder_traversal(my_tree.root); }आउटपुट
In-Order Traversal: 5 8 10 15 16 20 23
