Binary Search Tree (BST) Implementation Gaming Project in C++
|
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 Node defines 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 to nullptr. BST …
Binary Search Tree (BST) Implementation Gaming Project in C++ Read More »
