// BSTree.cpp

#ifndef BSTREE_CPP #define BSTREE_CPP

#include #include #include "BSTree.h"

using namespace std;

//--------------------------------------------------------------------

template < class DataType, class KeyType > BSTree::BSTreeNode::BSTreeNode(const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr)

// Creates a binary search tree node containing data item elem, left // child pointer leftPtr, and right child pointer rightPtr.

: dataItem(nodeDataItem), left(leftPtr), right(rightPtr)

{}

//--------------------------------------------------------------------

template < class DataType, class KeyType > BSTree::BSTree()

// Creates an empty tree.

: root(0)

{}

//--------------------------------------------------------------------

template < class DataType, class KeyType > BSTree::BSTree(const BSTree &source)

// Creates an empty tree.

: root(0)

{ //Add code here }

//--------------------------------------------------------------------

template < class DataType, class KeyType > BSTree& BSTree:: operator= (const BSTree &sourceTree)

// Sets a tree to be equivalent to the tree "source".

{ //Add code here }

//--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::copyTree(const BSTree &sourceTree)

// Sets a tree to be equivalent to the tree "source".

{ copyTreeHelper(root, sourceTree.root); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::copyTreeHelper(BSTreeNode *&p, const BSTreeNode *sourcePtr)

// Recursive helper function that helps set a tree to be equivalent to another tree.

{ if (sourcePtr != 0) { //cout << "Copy Condtructor is called" << endl; p = new BSTreeNode(sourcePtr->dataItem, 0, 0); copyTreeHelper(p->left, sourcePtr->left); copyTreeHelper(p->right, sourcePtr->right); } }

//-------------------------------------------------------------------- template < class DataType, class KeyType > BSTree:: ~BSTree()

// Frees the memory used by a tree.

{ clear(); }

//--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::insert(const DataType &newDataItem)

// Inserts newDataItem into a tree. If an data item with the same key // as newDataItem already exists in the tree, then updates that // data item's data with newDataItem's data.

{ //Add code here }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::insertHelper(BSTreeNode *&p, const DataType &newDataItem)

{ if (p == 0) // Insert //Add code here else if (newDataItem.getKey() < p->dataItem.getKey()) //Add code here // Search left else if (newDataItem.getKey() > p->dataItem.getKey()) //Add code here // Search right else //Add code here // Update }

//--------------------------------------------------------------------

template < class DataType, class KeyType > bool BSTree::retrieve(const KeyType& searchKey, DataType &searchDataItem) const

// Searches a tree for the data item with key searchKey. If the data item // is found, then copies the data item to searchDataItem and returns true. // Otherwise, returns false with searchDataItem undefined.

{ return retrieveHelper(root, searchKey, searchDataItem); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > bool BSTree::retrieveHelper(BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem) const

// Recursive helper function for retrieve. Searches the subtree // pointed to by p.

{ bool result; // Result returned

if (p == 0) { result = false; } else if (searchKey < p->dataItem.getKey()) { // Key is smaller than current node. Search to left. result = retrieveHelper(p->left, searchKey, searchDataItem); } else if (searchKey > p->dataItem.getKey()) { // Key is larger than current node. Search to right. result = retrieveHelper(p->right, searchKey, searchDataItem); } else { // Found the desired item //Add code here }

return result; }

//--------------------------------------------------------------------

template < class DataType, class KeyType > bool BSTree::remove(const KeyType& deleteKey)

// Removes the data item with key deleteKey from a tree. If the // data item is found, then deletes it from the tree and returns true. // Otherwise, returns false.

{ return removeHelper(root, deleteKey); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > bool BSTree::removeHelper(BSTreeNode *&p, const KeyType& deleteKey)

// Recursive helper function for remove. Searches the subtree // pointed to by p for the node with key deleteKey. If this node is // found, then does one of the following: // // - If the node is missing one or more children, then links // around it and deletes it. // // - Otherwise, uses cutRightmost to replace the data in the // node with the data in the rightmost descendant of the node's // left child and deletes that node.

{ BSTreeNode *delPtr; // Pointer to node to delete int result; // Result returned

if (p == 0) result = false; // Search failed else if (deleteKey < p->dataItem.getKey()) result = removeHelper(p->left, deleteKey); // Search left else if (deleteKey > p->dataItem.getKey()) result = removeHelper(p->right, deleteKey); // Search right else { // Found delPtr = p; if (p->left == 0) { //Add code here // No left child delete delPtr; } else if (p->right == 0) { //Add code here // No right child delete delPtr; } else // Node has both children: removing is more complex. {

// ** Start implemtation option #1 // Find node with largest key smaller than p's key. BSTreeNode* temp = p->left; while (temp->right) { //Add code here } // Copy node data to p p->dataItem = temp->dataItem; // And remove the node whose data was copied to p. removeHelper(p->left, temp->dataItem.getKey());

/* // ** Start implemtation option #2. Looks simpler here, // but there is all of cutRightmost to deal with. cutRightmost(p->left,delPtr); delete delPtr; */ } result = true; }

return result; }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::cutRightmost(BSTreeNode *&r, BSTreeNode *&delPtr)

// Recursive helper function for removeHelper in implementation // option #2. Traces down a sequence of right children. Copies the // data from the last node in the sequence into the node pointed // to delPtr, sets delPtr to point to the last node in the sequence, // and links around this node.

{ if (r->right != 0) cutRightmost(r->right, delPtr); // Continue down to the right else { delPtr->dataItem = r->dataItem; delPtr = r; r = r->left; } }

//--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::writeKeys() const

// Outputs the keys in a tree in ascending order.

{ writeKeysHelper(root); cout << endl; }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::writeKeysHelper(BSTreeNode *p) const

// Recursive helper for writeKeys. // Outputs the keys in the subtree pointed to by p.

{ if (p != 0) { //Add code here } }

//--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::clear()

// Removes all the nodes from a tree.

{ clearHelper(root); root = 0; }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::clearHelper(BSTreeNode *p)

// Recursive helper for clear. Clears the subtree pointed to by p.

{ if (p != 0) { // Use post-order traversal. Otherwise get into trouble by // referencing p->left and/or p->right after p had been deallocated. clearHelper(p->left); clearHelper(p->right); delete p; } }

//--------------------------------------------------------------------

template < class DataType, class KeyType > bool BSTree::isEmpty() const

// Returns true if a tree is empty. Otherwise returns false.

{ //Add code here }

//--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::showStructure() const

// Outputs the keys in a binary search tree. The tree is output // rotated counterclockwise 90 degrees from its conventional // orientation using a "reverse" inorder traversal. This operation is // intended for testing and debugging purposes only.

{ if (root == 0) cout << "Empty tree" << endl; else { cout << endl; showHelper(root, 1); cout << endl; } }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::showHelper(BSTreeNode *p, int level) const

// Recursive helper for showStructure. // Outputs the subtree whose root node is pointed to by p. // Parameter level is the level of this node within the tree.

{ int j; // Loop counter

if (p != 0) { showHelper(p->right, level + 1); // Output right subtree for (j = 0; j < level; j++) // Tab over to level cout << "\t"; cout << " " << p->dataItem.getKey(); // Output key if ((p->left != 0) && // Output "connector" (p->right != 0)) cout << "<"; else if (p->right != 0) cout << "/"; else if (p->left != 0) cout << "\\"; cout << endl; showHelper(p->left, level + 1); // Output left subtree } }

//-------------------------------------------------------------------- // Programming Exercise 2 //--------------------------------------------------------------------

template < class DataType, class KeyType > int BSTree::getHeight() const

// Returns the height of a tree.

{ return getHeightHelper(root); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > int BSTree::getHeightHelper(BSTreeNode *p) const

// Recursive helper for height. Returns the height of // the subtree pointed to by p -- that is, the length of the longest // path from the node pointed to by p to any leaf node.

{ int l, // Length of the longest path thru the left child r, // Length of the longest path thru the right child result; // Result returned

if (p == 0) result = 0; // Leaf node else { l = getHeightHelper(p->left) + 1; // Get height of left subtree r = getHeightHelper(p->right) + 1; // Get height of right subtree if (l >= r) // Return larger //Add code here else //Add code here }

return result; }

template < class DataType, class KeyType > int BSTree::getCount() const

// Returns the number of nodes in the tree

{ return getCountHelper(root); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > int BSTree::getCountHelper(BSTreeNode *p) const

// Recursive partner of the getCount() function. Returns the count of // the subtree pointed to by p -- that is, the number of nodes in the // left child + number of nodes in the right child + 1

{ //Add code here }

//-------------------------------------------------------------------- // Programming Exercise 3 //--------------------------------------------------------------------

template < class DataType, class KeyType > void BSTree::writeLessThan(const KeyType& searchKey) const

// Outputs the keys in a tree that are less than searchKey.

{ writeLTHelper(root, searchKey); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DataType, class KeyType > void BSTree::writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const

// Recursive helper function for writeLessThan. Outputs the keys // in the subtree pointed to by p that are less than searchKey.

{ if (p != 0) { writeLTHelper(p->left, searchKey); if (searchKey > p->dataItem.getKey()) { cout << p->dataItem.getKey() << endl; //Add code here } } }

#endif // #ifdef BSTREE_CPP