BST Class:

Make sure you study the BST/AVL discussion

Use your BST functions to implement a BST class:

template <typename T>
class BST{
public:
    BST();
    BST(const T *sorted_list, int size = -1);
    //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    BST(const BST<T> &copy_me);
    BST<T> &operator=(const BST<T> &rhs);
    ~BST();
    //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    void insert(const T &insert_me);

    void erase(const T &target);

    
    bool contains(const T &target)const;
    void clear_all();
    bool empty()const;
    friend ostream &operator<<(ostream &outs, const BST<T> &tree)
    {
        const bool debug = false;
        if (debug){
            cout<<"-------------------------------"<<endl;
            tree_print_debug(tree._root, 0, outs);
            cout<<". . . . . . . . . . . . . . . ."<<endl;
        }
        tree_print(tree._root, 0, outs);
        return outs;
    }
    BST<T> operator+=(const BST<T> &rhs);
    string pre_order();
    string in_order();
    string post_order();

private:
    tree_node<T>* _root;
};

Testing:

You will write individual functions that will test every aspect of this class. The insertion, the deletion, the copying and clearing and of course searching.

You will also write an interactive function that gives the user the following options:

[R]andom  [I]nsert  [C]clear  [S]earch  [E]rase      e[X]it: 

here is sample interaction:

[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 46
tree_node CTOR: item: 46:0
[46]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 22
tree_node CTOR: item: 22:0
[46]
    [22]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 41
tree_node CTOR: item: 41:0
[46]
        [41]
    [22]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 4
tree_node CTOR: item: 4:0
[46]
        [41]
    [22]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 8
tree_node CTOR: item: 8:0
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 84
tree_node CTOR: item: 84:0
    [84]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 96
tree_node CTOR: item: 96:0
        [96]
    [84]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 64
tree_node CTOR: item: 64:0
        [96]
    [84]
        [64]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 57
tree_node CTOR: item: 57:0
        [96]
    [84]
        [64]
            [57]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 56
tree_node CTOR: item: 56:0
        [96]
    [84]
        [64]
            [57]
                [56]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 50
tree_node CTOR: item: 50:0
        [96]
    [84]
        [64]
            [57]
                [56]
                    [50]
[46]
        [41]
    [22]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 10
tree_node CTOR: item: 10:0
        [96]
    [84]
        [64]
            [57]
                [56]
                    [50]
[46]
        [41]
    [22]
                [10]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 42
tree_node CTOR: item: 42:0
        [96]
    [84]
        [64]
            [57]
                [56]
                    [50]
[46]
            [42]
        [41]
    [22]
                [10]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: s
? 42
item is found. |42|        [96]
    [84]
        [64]
            [57]
                [56]
                    [50]
[46]
            [42]
        [41]
    [22]
                [10]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: s
? -42
item not found.
        [96]
    [84]
        [64]
            [57]
                [56]
                    [50]
[46]
            [42]
        [41]
    [22]
                [10]
            [8]
        [4]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: c

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: x   

=========================

================================
Press <RETURN> to close this window...