Binary Search Tree (BST) Implementation Gaming Project in C++

Projects Inventory

3 months ago

#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;
}

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 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 function insertRec.
  - 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 function searchRec.
- 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.
  - 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 true if the value matches the node’s data.
    - Recursively searches in the left or right subtree based on the value.
Main Function (main):
- Creates a BST object.
- 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.

Explanation

Related Posts: