Question 8 Given the binary search tree in Figure 15-18 of Chapter 15 , trace the removal algorithms when removing each of the following values from the tree. Begin with the original tree each time. a. 70 b. 20 c. 60

The following exercise must be implemented in C++. Here are the following headers that must be used with:

#ifndef _BINARY_TREE_INTERFACE #define _BINARY_TREE_INTERFACE template class BinaryTreeInterface { public : /** Tests whether this binary tree is empty. @return True if the binary tree is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Gets the height of this binary tree. @return The height of the binary tree. */ virtual int getHeight() const = 0; /** Gets the number of nodes in this binary tree. @return The number of nodes in the binary tree. */ virtual int getNumberOfNodes() const = 0; /** Gets the data that is in the root of this binary tree. @pre The binary tree is not empty. @post The roots data has been returned, and the binary tree is unchanged. @return The data in the root of the binary tree. */ virtual ItemType getRootData() const = 0; /** Replaces the data item in the root of this binary tree with the given data, if the tree is not empty. However, if the tree is empty, inserts a new root node containing the given data into the tree. @pre None. @post The data in the root of the binary tree is as given. @param newData The data for the root. */ virtual void setRootData( const ItemType& newData) = 0; /** Adds a new node containing the given data to this binary tree. @param newData The data for the new node. */ @post The binary tree contains a new node. @return True if the addition is successful, or false not. */ virtual bool add( const ItemType& newData) = 0; /** Removes the node containing the given data item from this binary tree. @param data The data value to remove from the binary tree. */ @return True if the removal is successful, or false not. */ virtual bool remove( const ItemType& data) = 0; /** Removes all nodes from this binary tree. */ virtual void clear() = 0; /** Gets a specific entry in this binary tree. @post The desired entry has been returned, and the binary tree is unchanged. If no such entry was found, an exception is thrown. @param anEntry The entry to locate. @return The entry in the binary tree that matches the given entry. @throw NotFoundException if the given entry is not in the tree. */ virtual ItemType getEntry( const ItemType& anEntry) const throw(NotFoundException) = 0; /** Tests whether a given entry occurs in this binary tree. @post The binary search tree is unchanged. @param anEntry The entry to find. @return True if the entry occurs in the tree, or false if not. */ virtual bool contains( const ItemType& anEntry) const = 0; /** Traverses this binary tree in preorder (inorder, postorder) and calls the function visit once for each node. @param visit A client-defined function that performs an operation on or with the data in each visited node. */ virtual void preorderTraverse( void visit(ItemType&)) const = 0; virtual void inorderTraverse( void visit(ItemType&)) const = 0; virtual void postorderTraverse( void visit(ItemType&)) const = 0; }; // end BinaryTreeInterface #endif

-----------------------------------------------------------------------------------------------------------------------------------------

#ifndef _BINARY_NODE_TREE #define _BINARY_NODE_TREE #include "BinaryTreeInterface.h" #include "BinaryNode.h" #include "PrecondViolatedExcep.h" #include "NotFoundException.h" template void BinaryNodeTree : public BinaryTreeInterface { private : BinaryNode* rootPtr; protected : //------------------------------------------------------------ // Protected Utility Methods Section: // Recursive helper methods for the public methods. //------------------------------------------------------------ int getHeightHelper(BinaryNode* subTreePtr) const ; int getNumberOfNodesHelper(BinaryNode* subTreePtr) const ; // Recursively deletes all nodes from the tree. void destroyTree(BinaryNode* subTreePtr); // Recursively adds a new node to the tree in a left/right fashion to // keep the tree balanced.

BinaryNode* balancedAdd(BinaryNode* subTreePtr, BinaryNode* newNodePtr); // Removes the target value from the tree by calling moveValuesUpTree // to overwrite value with value from child. BinaryNode* removeValue(BinaryNode* subTreePtr, const ItemType target, bool& success); // Copies values up the tree to overwrite value in current node until // a leaf is reached; the leaf is then removed, since its value is // stored in the parent. BinaryNode* moveValuesUpTree(BinaryNode* subTreePtr); // Recursively searches for target value in the tree by using a // preorder traversal. BinaryNode* findNode(BinaryNode* treePtr, const ItemType& target, bool& success) const ; // Copies the tree rooted at treePtr and returns a pointer to // the copy. BinaryNode* copyTree( const BinaryNode* treePtr) const ; // Recursive traversal helper methods: void preorder( void visit(ItemType&), BinaryNode* treePtr) const ; void inorder( void visit(ItemType&), BinaryNode* treePtr) const ; void postorder( void visit(ItemType&), BinaryNode* treePtr) const ; public : //------------------------------------------------------------ // Constructor and Destructor Section. //------------------------------------------------------------ BinaryNodeTree(); BinaryNodeTree( const ItemType& rootItem); BinaryNodeTree( const ItemType& rootItem, const BinaryNodeTree* leftTreePtr, const BinaryNodeTree* rightTreePtr); BinaryNodeTree( const BinaryNodeTree& tree); virtual ~BinaryNodeTree(); //------------------------------------------------------------ // Public BinaryTreeInterface Methods Section. //------------------------------------------------------------ bool isEmpty() const ; int getHeight() const ; int getNumberOfNodes() const ; ItemType getRootData() const throw (PrecondViolatedExcep); void setRootData( const ItemType& newData); bool add( const ItemType& newData); // Adds a node bool remove( const ItemType& data); // Removes a node void clear();

ItemType getEntry( const ItemType& anEntry) const throw (NotFoundException); bool contains( const ItemType& anEntry) const ; //------------------------------------------------------------ // Public Traversals Section. //------------------------------------------------------------ void preorderTraverse( void visit(ItemType&)) const ; void inorderTraverse( void visit(ItemType&)) const ; void postorderTraverse( void visit(ItemType&)) const ; //------------------------------------------------------------ // Overloaded Operator Section. //------------------------------------------------------------ BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide); }; // end BinaryNodeTree #include "BinaryNodeTree.cpp" #endif

-------------------------------------------------------------------------------------------------------------------------------------------------

#include "BinaryNodeTree.h" #include "BinaryNode.h" #include

////////////////////////////////////////////////////////////// // Protected Utility Methods Section //////////////////////////////////////////////////////////////

template int BinaryNodeTree::getHeightHelper(BinaryNode* subTreePtr) const { if (subTreePtr == nullptr) return 0; else return 1 + max(getHeightHelper(subTreePtr->getLeftChildPtr()), getHeightHelper(subTreePtr->getRightChildPtr())); } // end getHeightHelper

template BinaryNode* BinaryNodeTree::balancedAdd(BinaryNode* subTreePtr, BinaryNode* newNodePtr) { if (subTreePtr == nullptr) return newNodePtr; else { BinaryNode* leftPtr = subTreePtr->getLeftChildPtr(); BinaryNode* rightPtr = subTreePtr->getRightChildPtr(); if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr)) { rightPtr = balancedAdd(rightPtr , newNodePtr); subTreePtr->setRightChildPtr(rightPtr ); } else { leftPtr = balancedAdd(leftPtr, newNodePtr); subTreePtr->setLeftChildPtr(leftPtr); } // end if return subTreePtr; } // end if } // end balancedAdd

template BinaryNode* BinaryNodeTree::copyTree(const BinaryNode* treePtr) const { BinaryNode* newTreePtr = nullptr; // Copy tree nodes during a preorder traversal if (treePtr != nullptr) { // Copy node newTreePtr = new BinaryNode(treePtr->getItem(), nullptr, nullptr); newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr())); newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr())); } // end if return newTreePtr; } // end copyTree

template void BinaryNodeTree::destroyTree(BinaryNode* subTreePtr) { if (subTreePtr != nullptr) { destroyTree(subTreePtr->getLeftChildPtr()); destroyTree(subTreePtr->getRightChildPtr()); delete subTreePtr; } // end if } // end destroyTree

////////////////////////////////////////////////////////////// // Protected Tree Traversal Sub-Section //////////////////////////////////////////////////////////////

template void BinaryNodeTree::inorder(void visit(ItemType&), BinaryNode* treePtr) const { if (treePtr != nullptr) { inorder(visit, treePtr->getLeftChildPtr()); ItemType theItem = treePtr->getItem(); visit(theItem); inorder(visit, treePtr->getRightChildPtr()); } // end if } // end inorder

////////////////////////////////////////////////////////////// // PUBLIC METHODS BEGIN HERE //////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////// // Constructor and Destructor Section //////////////////////////////////////////////////////////////

template BinaryNodeTree::BinaryNodeTree() : rootPtr(nullptr) { } // end default constructor

template BinaryNodeTree::BinaryNodeTree(const ItemType& rootItem) { rootPtr = new BinaryNode(rootItem, nullptr, nullptr); } // end constructor

template BinaryNodeTree::BinaryNodeTree(const ItemType& rootItem, const BinaryNodeTree* leftTreePtr, const BinaryNodeTree* rightTreePtr) { rootPtr = new BinaryNode(rootItem, copyTree(leftTreePtr->rootPtr), copyTree(rightTreePtr->rootPtr)); } // end constructor

template BinaryNodeTree::BinaryNodeTree(const BinaryNodeTree& treePtr) { rootPtr = copyTree(treePtr.rootPtr); } // end copy constructor

template BinaryNodeTree::~BinaryNodeTree() { destroyTree(rootPtr); } // end destructor

////////////////////////////////////////////////////////////// // Public BinaryTreeInterface Methods Section //////////////////////////////////////////////////////////////

template bool BinaryNodeTree::add(const ItemType& newData) { BinaryNode* newNodePtr = new BinaryNode(newData); rootPtr = balancedAdd(rootPtr, newNodePtr); return true; } // end add

} // end contains

////////////////////////////////////////////////////////////// // Public Traversals Section //////////////////////////////////////////////////////////////

template void BinaryNodeTree::inorderTraverse(void visit(ItemType&)) const { inorder(visit, rootPtr); } // end inorderTraverse

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#ifndef _BINARY_NODE #define _BINARY_NODE

template class BinaryNode { private: ItemType item; // Data portion BinaryNode* leftChildPtr; // Pointer to left child BinaryNode* rightChildPtr; // Pointer to right child

public: BinaryNode(); BinaryNode(const ItemType& anItem); BinaryNode(const ItemType& anItem, BinaryNode* leftPtr, BinaryNode* rightPtr);

void setItem(const ItemType& anItem); ItemType getItem() const; bool isLeaf() const;

BinaryNode* getLeftChildPtr() const; BinaryNode* getRightChildPtr() const; void setLeftChildPtr(BinaryNode* leftPtr); void setRightChildPtr(BinaryNode* rightPtr); }; // end BinaryNode

#include "BinaryNode.cpp"

#endif

FIGURE 15-18 A tree for Exercises l, 2,6, 7,11, and 23 20 70