Answer to Question #295698 in C++ for Roe

Question

Write a program that contains the following functions

1)Make Binary search tree

2)search element in bst

3)display bst

4)find the maximum value in bst

5)find the minimum value in bst

6)display the leaf nodes

Requirements :

No global decelerations

Run test the functions in main

Answer 1

#include <iostream>
using namespace std;


class BST {
public:
    BST() { root = nullptr; }
    BST(int* arr, int n);
    ~BST() { remove(root); }
    void add(int v) { root = add(root, v); }
    void display() { display(root); }
    bool search(int v) { return search(root, v); }
    int min() { return min(root); }
    int max() { return max(root); }
    void display_leaf() { 
        display_leaf(root); 
        cout << endl;
    }


private:
    struct Node {
        int data;
        Node* left;
        Node* right;
        Node(int v) {
            data = v;
            left = right = nullptr;
        }
    };
    Node* root;
    Node* add(Node* r, int v);
    void display(Node* r);
    bool search(Node* r, int v);
    int min(Node* r);
    int max(Node* r);
    void display_leaf(Node* r);
    void remove(Node* r);
};


BST::BST(int *arr, int n) {
    root = nullptr;
    for (int i=0; i<n; i++) {
        root = add(root, arr[i]);
    }
}


void BST::remove(Node* r) {
    if (!r) {
        return;
    }
    remove(r->left);
    remove(r->right);
    delete r;
}


BST::Node* BST::add(Node* r, int v) {
    if (!r) {
        return new Node(v);
    }
    if ( v < r->data) {
        r->left = add(r->left, v);
    }
    else {
        r->right = add(r->right, v);
    }
    return r;
}


void BST::display(Node* r) {
    if (!r) {
        cout << "#";
        return;
    }
    cout <<"(data=" << r->data << ": left->";
    display(r->left);
    cout << "; right->";
    display(r->right);
    cout << ")";
}


bool BST::search(Node* r, int v) {
    if (!r) {
        return false;
    }
    if (r->data == v) {
        return true;
    }
    if (v < r->data) {
        return search(r->left, v);
    }
    else {
        return search(r->right, v);
    }
}


int BST::min(Node* r) {
    if (r->left) {
        return min(r->left);
    }
    return r->data;
}


int BST::max(Node* r) {
    if (r->right) {
        return max(r->right);
    }
    return r->data;
}


void BST::display_leaf(Node* r) {
    if (!r->left && !r->right) {
        cout << "#" << r->data << "#  ";
    }
    if (r->left) {
        display_leaf(r->left);
    }
    if (r->right) {
        display_leaf(r->right);
    }
}


int main() {
    int arr[] = { 8, 5, 12, 7, 9, 4, 13, 6, 22};
    int n = sizeof(arr) / sizeof(arr[0]);
    BST bst(arr, n);


    cout << "bst:" << endl;
    bst.display();
    cout << endl << "Leaf:" << endl;
    bst.display_leaf();


    cout << endl << "Min: " << bst.min() << endl;
    cout << "Max: " << bst.max() << endl << endl;


    int x;
    cout << "Enter a number to search: ";
    cin >> x;
    if ( bst.search(x)) {
        cout << "Value was found" << endl;
    }
    else {
        cout << "Value was not found" << endl;
    }

    return 0;
}