MP 5

Binary Search Tree*

The purpose of this assignment is to implement a Binary Search Tree as a template class. The basic structure for the class is given below.

    // the node structure
    template <class Item>
    struct BSTNode {
        Item data;
        BSTNode *left;
        BSTNode *right;
    };

    template <class Item>
    class BST
    {
    public:
        // constructs an empty BST
        BST();

        // constructs a BST that is a copy of another BST (copy constructor)
        BST(const BST& source);

        // returns the dynamically allocated memory
        ~BST();

        // adds a new item to the BST
        void insert(const Item& entry);

        // calls del
        void remove(const Item& target);

        // searches the BST for target and returns true if it was found, in which
        // case the found Item is copied into result, otherwise false is returned
        bool find(const Item& target, Item& result) const;

        // finds the maximum value in the BST and returns true if successful, in which
        // case the maximum value is copied into result, otherwise false is returned
		// the maximum valued item is removed from the BST
        bool returnMax(Item& result);

        // finds the minimum value in the BST and returns true if successful, in which
        // case the minimum value is copied into result, otherwise false is returned
		// the minimum valued item is removed from the BST
        bool returnMin(Item& result);

       // assigns one BST to another BST
        void operator =(const BST& source);
        
        // returns the number of nodes in the BST
        long size() const;
        
        // returns true if the BST is currently empty
        bool is_empty() const;

       // traverses the tree inorder and prints values
       void printInorder() const;

       // traverses the tree preorder and prints values
       void printPreorder() const;

       // traverses the tree postorder and prints values
       void printPostorder() const;

    private:
        // returns all the subtree's nodes to the heap and sets root to NULL
        void clear(BSTNode<Item>*& root);

        // returns a structural copy of the subtree
        BSTNode<Item>* copy(BSTNode<Item>* root);

        // returns a newly created node with no children and entry in the data field
        BSTNode<Item>* create_leaf_node(const Item& entry);

        // deletes the largest item from the subtree and returns the deleted item
        Item remove_max(BSTNode<Item>*& root);

        // deletes the smallest item from the subtree and returns the deleted item
        Item remove_min(BSTNode<Item>*& root);

        // deletes a given item from the subtree
        void del(BSTNode<Item>*& root, const Item& target);

        // this is the BST's root pointer
        BSTNode<Item>* root;

        // this variable counts the number of nodes in the BST
        long num_nodes;
    };

The Assignment

Implement the BST class as shown above. The requirements are:

1. Implement all public methods as shown. You may implement and private methods that you wish, but implementing the ones noted above should make the implementation easier.
2. You must write a test driver for the class that exercises all methods you define. Your test driver should implement the BST class for both float and int types (see hint code below, main function). Your test driver should populate the tree with not less than 10 values for each type.
3. Assume that your BST will not have to deal with duplicate values. If you would like to implement the BST with duplicate values, see extra credit below.
4. You can gain extra credit for implementing the overloaded + operator. See extra credit below.

Hint

The following methods have been supplied to aid in your implementation:

		template <class Item>
		bool BST<Item>::is_empty() const {
			if(root == NULL) return true;
			else return false;
		}

		template <class Item>
		long BST<Item>::size() const {
			return num_nodes;
		}

		template <class Item>
		BSTNode<Item>* create_leaf_node(const Item& entry) {
			BSTNode<Item> * temp = new BSTNode<Item>;
			temp->data = entry;
			return temp;
		}

Extra Credit

You may implement the following items for extra credit. Clearly indicate on your submission that you have implemented these.

1. Implement BST allowing for duplicate entries.
2. Implement BST with a "+" operator. The "+" operator will allow combining two or more BST's as follows:

   BST<int> A(), B(), C(); A = B + C;

What You'll Turn In

1. A printout of your source code
2. A diskette containing your source code, clearly labeled with:

• your name, printed
• the course number
• the assignment number