|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <iostream> using namespace std; // Node structure for the Binary Search Tree struct Node { int data; Node* left; Node* right; Node(int value) : data(value), left(nullptr), right(nullptr) {} }; // Binary Search Tree class class BST { public: BST() : root(nullptr) {} // Insert a new value into the BST void insert(int value) { root = insertRec(root, value); } // Perform in-order traversal of the BST void inorder() const { inorderRec(root); cout << endl; } // Search for a value in the BST bool search(int value) const { return searchRec(root, value); } private: Node* root; // Recursive insert function Node* insertRec(Node* node, int value) { if (node == nullptr) { return new Node(value); } if (value < node->data) { node->left = insertRec(node->left, value); } else if (value > node->data) { node->right = insertRec(node->right, value); } return node; } // Recursive in-order traversal function void inorderRec(Node* node) const { if (node != nullptr) { inorderRec(node->left); cout << node->data << " "; inorderRec(node->right); } } // Recursive search function bool searchRec(Node* node, int value) const { if (node == nullptr) { return false; } if (value == node->data) { return true; } if (value < node->data) { return searchRec(node->left, value); } return searchRec(node->right, value); } }; int main() { BST tree; // Insert values into the BST tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); // Perform in-order traversal cout << "In-order traversal: "; tree.inorder(); // Search for values in the BST int searchValue = 40; if (tree.search(searchValue)) { cout << searchValue << " is present in the BST." << endl; } else { cout << searchValue << " is not present in the BST." << endl; } searchValue = 90; if (tree.search(searchValue)) { cout << searchValue << " is present in the BST." << endl; } else { cout << searchValue << " is not present in the BST." << endl; } return 0; } |
Explanation
- Node Structure:
struct Nodedefines the structure of a node in the BST.int data: Stores the value of the node.Node* left: Pointer to the left child.Node* right: Pointer to the right child.Node(int value): Constructor to initialize a node with a given value and set child pointers tonullptr.
- BST Class:
- Private Members:
Node* root: Pointer to the root of the tree.
- Public Methods:
void insert(int value): Inserts a new value into the BST by calling the recursive helper functioninsertRec.void inorder() const: Performs an in-order traversal of the BST and prints the values.bool search(int value) const: Searches for a value in the BST by calling the recursive helper functionsearchRec.
- Private Methods:
Node* insertRec(Node* node, int value): Recursively inserts a value into the tree.- Creates a new node if the current node is
nullptr. - Recursively inserts into the left or right subtree based on the value.
- Creates a new node if the current node is
void inorderRec(Node* node) const: Recursively performs in-order traversal of the tree.- Visits left subtree, prints the node data, and then visits the right subtree.
bool searchRec(Node* node, int value) const: Recursively searches for a value in the tree.- Returns
trueif the value matches the node’s data. - Recursively searches in the left or right subtree based on the value.
- Returns
- Private Members:
- Main Function (
main):- Creates a
BSTobject. - Inserts several values into the BST.
- Performs in-order traversal and prints the result.
- Searches for specific values and prints whether they are present in the BST.
- Creates a