## Description

The Bag Class with a Binary Search Tree, adapted from Michael Main’s version

The Assignment:

Implement the BSTreeBag template class, using a binary search tree to store the items.

Purposes:

Ensure that you understand and can use binary search trees and recursive algorithms for processing them.

Before Starting:

Read this handout and the Trees chapter (pp. 507-535) in Carrano.

Due Dates:

Part 1: Constructors, destructor, operator=, size required in lab due Saturday, Nov 16, 8 am.

Insert, count functions: 2% bonus if you finish and turn this in by Saturday, Nov 16, 8

am.

Part 2: The rest of the work, including insert and count: due Saturday, Nov 23, 8 am. Files that you must write:

BSTTreeBag.h: Header file for this version of the BSTreeBag class. You don’t have to write much of this file unless you add helper functions. Just copy our version and add your name and other information at the top.

BSTreeBag.cxx: The implementation file for the new BSTreeBag class. This time, you must write this from scratch—though your labs next week will help.

Other files that you may find helpful:

bintree.h and bintree.cxx. These define the binary tree node template class. You don’t have to write anything for these. NOTE: This version of the binary tree node template has the return values from the non-const versions of the **l****eft()** and **right()** functions return a reference to the pointer in the node. This is indicated by the & symbol for them in bintree.h and bintree.cxx:

**binary_tree_node*& left( )**

The use of a “reference return type” (indicated by the ampersand) in the return value has two advantages that simplify the material. It now allows a direct assignment such as: **p->left() = NULL**. This is not a huge advantage, since the same thing can be accomplished by using the **set_left **function.

The expression **p->left()** can be passed as the argument to a function such as: **tree_clear(p-**

**>left())**; The parameter of **tree_clear** is a reference parameter, so that any changes that **tree_clear** makes to **p->left()** will now affect the actual left pointer in the **binary_tree_node<ItemType>* p**. In this example, the **tree_clear** function does set its

parameter to **NULL**, so that the total effect of **tree_clear(p->left())** is to clear the left subtree of

**p**** **and to set **p**** **‘s left pointer to **NULL**.

In the case of **tree_clear**, this is not a huge advantage because we could have just set **p**‘s left pointer to **NULL** ourselves. But, in this assignment, there are two functions, **bst_remove** and **bst_remove_max**, which are easier to write if we can use **root_ptr->left()** and **root_ptr-**

**>right()** as the parameters of recursive calls. See my implementations in BSTreeBag.h for details.

BSTreeBagTest.cxx: A simple interactive test program.

BSTreeBagExam.cxx: A non-interactive test program that will be used to grade the correctness of your bag class.

Makefile: for compiling the assignment.

The Bag Class Using a Binary Search Tree

Discussion of the Assignment

This assignment is another template class. I am giving you the code for bintree.h and bintree.cxx, which define a template class for the **binary_tree_node**. Use these files, but do not change them. You’ll

see the specification for the whole basic bintree class in bintree.h: We begin by making a namespace for

your class (the test code has to say

**using hw6;**

to use **binary_tree_nodes** without having to say **h****w6::binary_tree_node** all the time.)

**namespace hw6**

**{**

**template <class ItemType> // bag holds any ItemType class binary_tree_node // class name**

**{**

**public:**

**// TYPEDEF**

**typedef ItemType value_type; // comparable ItemTypes typedef unsigned int size_type;**

**// CONSTRUCTOR // if data was not supplied,**

**// it gets initialized here.**

**binary_tree_node(**

**const ItemType& init_data = ItemType( ),**

**binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL**

**)**

**{**

**data_field = init_data;**

**left_field = init_left;**

**right_field = init_right;**

**}**

**// MODIFICATION MEMBER FUNCTIONS ItemType& data( ) { return data_field; }**

**binary_tree_node*& left( ) { return left_field; }**

**binary_tree_node*& right( ) { return right_field; }**

**// CONST MEMBER FUNCTIONS**

**const ItemType& data( ) const { return data_field; }**

**const binary_tree_node* left( ) const**

**{ return left_field; }**

**const binary_tree_node* right( ) const**

**{ return right_field; }**

**bool is_leaf( ) const**

**{ return (left_field == NULL) &&**

**(right_field == NULL); }**

Next come your private member variables for your state as a node in a binary tree:

**private:**

**ItemType data_field;**

**binary_tree_node *left_field;**

**binary_tree_node *right_field;**

**};**

Last come the nonmember functions for making trees from these binary tree nodes.

The first 3 do tree traversals (remember there are 3 orderings) and pass in a Process as a function to be done on every element on the tree (now we are passing functions like they’re data, mind you). I didn’t actually use these functions for this homework, but they’re here if you want them.

**// NON-MEMBER FUNCTIONS for the binary_tree_node<ItemType>:**

**template <class Process, class BTNode>**

**void inorder(Process f, BTNode* node_ptr);**

**template <class Process, class BTNode>**

**void preorder(Process f, BTNode* node_ptr);**

**template <class Process, class BTNode>**

**void postorder(Process f, BTNode* node_ptr);**

The next one, print, is very useful for displaying your tree:

**template <class ItemType, class SizeType>**

**void print(binary_tree_node<ItemType>* node_ptr, SizeType depth);**

We have a tree_clear function to destroy a tree (which has to happen recursively without losing the links):

**template <class ItemType>**

**void tree_clear(binary_tree_node<ItemType>*& root_ptr);**

We have a tree_copy function to make a deep copy of a full tree (also recursive):

**template <class ItemType>**

**binary_tree_node<ItemType>* tree_copy(const binary_tree_node<ItemType>***

**root_ptr);**

Finally, the code has a recursive method to count up all the nodes in the tree and return that number:

**template <class ItemType>**

**typename binary_tree_node<ItemType>::size_type tree_size(const**

**binary_tree_node<ItemType>* node_ptr);**

We’ll discuss the bintree functions in class, but they should take care of a lot of the binary search tree functions, as long as you can call them properly. I used print for debugging a lot. (Start print’s depth at

0, and depth will count up in recursions and terminate properly.)

Your bintree.cxx and bintree.h files give you the basic functions of a binary tree, but you are writing a class that extends this binary tree into a *binary search tree*. In the textbook, Carrano’s binary search tree has the rule that a binary search tree node has data that is greater than all the data in its left subtree, and its data is also less than all the data in its right subtree. But this doesn’t let us add duplicates to a tree, which is overly restrictive. We’ll relax this rule to say that the data in a binary search tree node is >= the data in its left subtree, and < the data in its right subtree. Now we can put duplicate entries in and not lose them.

In BSTreeBag.h, you will see the functions you need to create in the BSTreeBag.cxx file. These are template functions, like the bintree.cxx and bintree.h ones. You can use the functions in bintree to get this done; it will help you keep your code short and safe.

**#ifndef BAG6_H**

**#define BAG6_H**

**#include <cstdlib> // Provides NULL and size_t**

**#include “bintree.h” // Provides binary_tree_node and related**

**functions**

**namespace hw6**

**{**

**template <class ItemType>**

**class BSTreeBag**

**{**

**public:**

**// TYPEDEFS**

**typedef unsigned int size_type;**

**typedef ItemType value_type;**

**// CONSTRUCTORS and DESTRUCTOR BSTreeBag( );**

**BSTreeBag(const BSTreeBag& source);**

**~BSTreeBag( );**

**// MODIFICATION functions**

**size_type erase(const ItemType& target);**

**bool erase_one(const ItemType& target);**

**void insert(const ItemType& entry);**

**void operator +=(const BSTreeBag& addend);**

**void operator =(const BSTreeBag& source);**

**// CONSTANT functions size_type size( ) const;**

**size_type count(const ItemType& target) const;**

**private:**

**addroot_ptr);**

**};**

**// Root pointer of binary search tree binary_tree_node<ItemType> *root_ptr;**

**void insert_all(binary_tree_node<ItemType>***

**// NONMEMBER functions for the BSTreeBag<ItemType> template class template <class ItemType>**

**BSTreeBag<ItemType> operator +(const BSTreeBag<ItemType>& b1, const BSTreeBag<ItemType>& b2);**

**}**

**#include “BSTreeBag.cxx” // Include the implementation.**

**#endif**

- 1. BASIC BINARY SEARCH TREE FUNCTIONS (start here)

Begin (as we always must) by considering a constructor. Don’t forget the template line for each of these

functions. Like this:

**template <class ItemType> BSTreeBag<ItemType>::BSTreeBag()**

**{**

**// ??**

**}**

Your Bag should set its **root_ptr** to **NULL** here. Since no numbers have yet been added, we aren’t storing any nodes yet. For us, an empty tree means the **root_ptr** is **NULL**, always. That’s all this constructor needs to do. Here’s a beautiful sketch of the memory right now for this newly made bag:

Your copy constructor, next, would benefit by looking at the **tree_copy** function in bintree.h and getting that to work.

Your destructor, likewise, would probably use **tree_clear**.

Your assignment operator should (among other things) make a call to **tree_clear** if needed, and it should also use **tree_copy**.

Along these same lines, write size. The header for this needs a **typename** that’s got the class namespace and the unsigned integer type we defined there. (It’s a hassle; I’ll go over it more, but this is needed to stop the compiler from kicking and screaming and punching.)

**const**

**typename BSTreeBag<ItemType>::size_type BSTreeBag<ItemType>::size( )**

All of these functions should go pretty quickly once you figure out what’s already been written. And if you do that, your memory managing functions are mostly done except for the insert and erase methods. Be sure you have this done early on and working by Friday at the latest, so you can finish the rest.

Upload what you have for the lab this week.

- 2. INSERTING AN ITEM INTO A BINARY SEARCH TREE

The next steps are to **insert** an **entry**, so you have a tree to play with. Remember that you always

know the tree’s **root_ptr**** **in this code, since that is a member of the class.

**void BSTreeBag<ItemType>::insert(const ItemType& entry)**

This involves handling one special case, where you’re inserting into an empty tree like the one that your default constructor made. You can tell if that’s true, provided that you set **root_ptr** correctly in that constructor. If so, say

**root_ptr = new binary_tree_node<ItemType>(entry);**

to make a new node on the heap (with left and right child pointers **== NULL**, and data containing the **entry**). The address of this node will now be stored in your **root_ptr**. In that case, your **insert** is done. In the example below, we’ve inserted 76 into an empty binary search tree of integers.

If the tree already has data in it, though, the code has to put the new **entry** in the right place. This works a lot like the method for searching for an item in a tree (as discussed quite ably in the trees chapter of Carrano’s book). In the example below, we have added 23 and 97 to the tree above:

Later, if we add more numbers (59, 103, 8), we’ll see:

One way to find the right place to insert a new **entry** is is to define a boolean variable called **done**, which starts as **false** (we have done nothing yet!) and a node pointer (**binary_tree_node<ItemType>* cursor**), which starts as **root_ptr**. Then, while **done** remains **false**,

If the data at the **cursor** is greater than or equal to the **entry**,

there.

If the **cursor** has no left child (its **left()**pointer is **N****ULL**), you can add the new **entry**

In this case, add the new binary_tree_node with this **e****ntry** as the left child

**cursor->left() = new binary_tree_node<ItemType>(entry);**

and note that you are now **done**. else, keep looking in the left subtree

**cursor = cursor->left();**

Else, similar logic applies to the right subtree.

Notice that **cursor->left()** is now returning a **binary_tree_node<ItemType>*&**, and the reference return type allows us to assign to it. This change sticks around after the code finishes, so you have really added it. Slick.

- 3. ERASING AN ITEM FROM A BINARY SEARCH TREE

To erase an item from a binary search tree is harder. We usually have to replace the erased item with something else to keep the tree an honest binary search tree. Erasing is complicated enough that we need 3 helper functions for all of the cases. One is **bst_remove**. This corresponds to erase_one; your public function erase_one will call your helper function **bst_remove** to do its whole job.

3a. **bst_remove**

The code I used has a second helper function called **b****st_remove_max** that **bst_remove** might need to use. But first, let’s talk about **bst_remove**. **bst_remove** removes a single copy of a **target** from a tree, and updates the **root_ptr** (and the others) as needed. It returns **true** if it found the **target** to remove, and **false** if it did not.

**bool bst_remove(binary_tree_node<ItemType>*& root_ptr, const ItemType&**

**target)**

The first case for **bst_remove** to handle is when the **root_ptr == NULL**. In this case, we can return **false** right away; there is no search tree left to remove an item from. That’s a base case for the recursion.

Else, if the **root_ptr**’s data is greater than the **target**, we must look in the left subtree for the item to remove. Make a recursive call using the left child of the **root_ptr**:

**return bst_remove(root_ptr->left(), target);**

Else if the **root_ptr**’s data is less than the **target**, look in the right subtree; do something like the line above;

Else, you’ve found the **target** at this **root_ptr**. Congratulations. Things now get complicated:

If the **root_ptr** has no left child, then you can delete **root_ptr**, but you want to replace it with its right child (even though that might be **NULL**, it’s ok).

**binary_tree_node<ItemType>* old_root_ptr = root_ptr;**

**root_ptr = root_ptr->right(); // replace with right child**

**delete old_root_ptr; // no leaks**

Consider our tree again.

To reinforce this example, suppose we wish to delete the 97. Here is what should happen:

Else, you are removing a **t****arget** in the middle of the tree with children, which is harder. You’ll probably have to replace this removed **target** with another entry in the tree to keep it a valid binary search tree. In this case, the best thing to do is to replace the **target** we’re deleting with the largest item in our left subtree. Suppose we want to delete the 76 from our tree and illustrate this example. Here is what should happen:

This function’s handled by the **bst_remove_max** function. Done correctly, this lets us replace our own data with the item we find there:

**bst_remove_max(root_ptr->left(), root_ptr->data());**

Now all your **bst_remove** cases should be done.

3b. **bst_remove_max**

Back to **bst_remove_max**, which removes the largest item from a tree and writes this item back by reference to **removed** using a reference input parameter):

**void bst_remove_max(binary_tree_node<ItemType>*& root_ptr, ItemType&**

**removed)**

This means that when you find the **binary_tree_node<ItemType>*** with the maximum value (call that node **frodo** here), you say

**removed = frodo->data(); // function remembers removed item bst_remove_max **must consider 2 recursive cases.

The first is that it has been given a **root_ptr**** **with no right child. In this case, the data in **root_ptr**** **is

what needs to be removed, as above. We want to delete this **root_ptr**** **node, too, but carefully.

**binary_tree_node<ItemType>* old_root_ptr = root_ptr;**

If **root_ptr**’s right child is missing, we can replace the node we are deleting with its left child without breaking the rules of a binary search tree:

**root_ptr = root_ptr->left(); // copy left child to root’s address**

Now we can delete the **old_root_ptr**.

The second case is when the **root_ptr** has a right child, and we should look there for even bigger items. The code below will update the right child (lvalue!) and the data (lvalue!) automatically.

**bst_remove_max(root_ptr->right(), root_ptr->data());**

3c. **bst_remove_all**

Erasing all the items in a tree requires you to write **bst_remove_all**. This works like **bst_remove**, but if **bst_remove_all** finds and removes the target, it must still keep looking in case more copies of the target exist. When you write this, have **erase** call **bst_remove_all** and you are done.

- 4. COUNTING UP THE COPIES OF AN ITEM IN A BINARY SEARCH TREE

Counting the copies of a **target** item in the tree uses that **size_type** again (compiler no kick, no scream).

**typename BSTreeBag<ItemType>::size_type**

**BSTreeBag<ItemType>::count(const ItemType& target) const**

This requires us to walk a **b****inary_tree_node<ItemType>* cursor **from the **root_ptr** down through the tree, looking for more copies of **target** and counting our **answer** up with each one we find. Initialize your **answer** to 0. Start **cursor** out as **root_ptr**.

While the **cursor** is not **N****ULL**, if the data at **cursor** is equal to the **target**, increment the **answer** to

1.

If the data at the **cursor** is greater than or equal to the **target**, return **answer + **the count in the left child. Else, if the data is less than the **target**, return the count in the right child.

- 5. ADDING ITEMS TO A BINARY SEACH TREE WITH +:
**operator+=**,**operator+**, and**insert_all**

To implement **operator+=**, we add the helper function **insert_all**:

**void BSTreeBag<ItemType>::insert_all(binary_tree_node<ItemType>***

**addroot_ptr)**

Here, if the **addroot_ptr** is not **NULL**, we insert its data into ourselves, and call

**insert_all(addroot_ptr->left());**

**// and one other thing you can deduce from the line above.**

Now, **operator+=** can check for self assignment (very important). If the assignment’s NOT something like **b += b**, calling **insert_all** directly will work to do the job. If it is like **b += b**, though, we need to double **b**. For this, make a copy of the **addroot_ptr**, use that as the root to **insert_all**, and then clear out the copy. Else, what bad thing can happen? Ponder that.

When you have **operator+=** working, use it to make **operator+**.

- 6. SOME HINTS:

Work piece by piece. Comment out the tests you can’t pass in the functions.

Since this is a template class, debugging can be more difficult (some debuggers don’t permit breakpoints in a template function.) To help in debugging, you can call **print(root_ptr, 0) **in a program to print the binary search tree for the bag you’re changing. But clean those out before you submit the code.

If you use our Makefile, you might notice that the BSTreeBag and bintree templates in the .cxx files are never compiled on their own, but in order to create BSTreeBagTest and BSTreeBagExam, all the template files must be present in the current directory.

Most of your grade will be based on the correctness of your implementation. However, the TAs will also look at your work and assign some points for clarity and programming style. Make sure that your name is on all your work.