the followiing code is based on the binary tree letters but itwont compile 4947127
The followiing code is based on the binary tree letters but itwont compile —————————————————————————————————————- #ifndef _BINARY_NODE #define _BINARY_NODE /** A class of nodes for a link-based binary tree. */ template class BinaryNode { private: ItemType item; // Data portion BinaryNode* leftChildPtr; // Pointerto left child BinaryNode* rightChildPtr; // Pointer to rightchild 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 /** @author Frank M. Carrano and Tim Henry * @file BinaryNode.cpp */ // Copyright (c) 2013 __Pearson Education__. Allrights reserved. #include template BinaryNode::BinaryNode() : item(nullptr),leftChildPtr(nullptr), rightChildPtr(nullptr) { } // end default constructor template BinaryNode::BinaryNode(const ItemType&anItem) : item(anItem),leftChildPtr(nullptr), rightChildPtr(nullptr) { } // end constructor template BinaryNode::BinaryNode(const ItemType&anItem, BinaryNode*leftPtr, BinaryNode*rightPtr) : item(anItem),leftChildPtr(leftPtr), rightChildPtr(rightPtr) { } // end constructor template void BinaryNode::setItem(const ItemType&anItem) { item = anItem; } // end setItem template ItemType BinaryNode::getItem() const { return item; } // end getItem template bool BinaryNode::isLeaf() const { return ((leftChildPtr ==nullptr) && (rightChildPtr == nullptr)); } template voidBinaryNode::setLeftChildPtr(BinaryNode*leftPtr) { leftChildPtr = leftPtr; } // end setLeftChildPtr template voidBinaryNode::setRightChildPtr(BinaryNode*rightPtr) { rightChildPtr =rightPtr; } // end setRightChildPtr template BinaryNode*BinaryNode::getLeftChildPtr() const { return leftChildPtr; } // endgetLeftChildPtr template BinaryNode*BinaryNode::getRightChildPtr() const { return rightChildPtr; } // endgetRightChildPtr #endif /** @author Frank M. Carrano and Tim Henry * @file BinaryNodeTree.h (Listing 16-3) */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #ifndef _BINARY_NODE_TREE #define _BINARY_NODE_TREE #include #include “BinaryTreeInterface.h” #include “BinaryNode.h” #include “PrecondViolatedExcep.h” #include “NotFoundException.h” #include /** ADT binary tree: Link-based implementation. */ template class BinaryNodeTree : publicBinaryTreeInterface { private: BinaryNode* rootPtr; protected: int getHeightHelper(BinaryNode* subTreePtr)const; int getNumberOfNodesHelper(BinaryNode*subTreePtr) const; void destroyTree(BinaryNode* subTreePtr); //Recursively deletes all nodes from the tree. BinaryNode*balancedAdd(BinaryNode* subTreePtr,BinaryNode* newNodePtr); // Removes the target value from the tree by callingmoveValuesUpTree to overwrite value with value from child. BinaryNode*removeValue(BinaryNode* subTreePtr,const ItemTypetarget, bool& success); // Copies values up the tree to overwrite value in current nodeuntil a leaf is reached; the leaf is then removed, since its valueis stored in the parent. BinaryNode*moveValuesUpTree(BinaryNode* subTreePtr); // Recursively searches for target value in the tree by using apreorder traversal. BinaryNode* findNode(BinaryNode*treePtr, const ItemType& target, bool& success) const; // Copies the tree rooted at treePtr and returns a pointer tothe copy. BinaryNode* copyTree(constBinaryNode* 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, constBinaryNodeTree* leftTreePtr, constBinaryNodeTree* rightTreePtr); BinaryNodeTree(const BinaryNodeTree&tree); virtual ~BinaryNodeTree(); // Public BinaryTreeInterface Methods Section. bool isEmpty() const; bool add(const ItemType& newData); // Adds a node bool remove(const ItemType& data); // Removes a node void clear(); ItemType getEntry(const ItemType& anEntry) const; 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 template intBinaryNodeTree::getHeightHelper(BinaryNode*subTreePtr) const { if (subTreePtr ==nullptr) return 0; else return 1 +max(getHeightHelper(subTreePtr->getLeftChildPtr()),getHeightHelper(subTreePtr->getRightChildPtr())); } // end getHeightHelper template intBinaryNodeTree::getNumberOfNodesHelper(BinaryNode*subTreePtr) const { if (subTreePtr ==nullptr) return 0; else return 1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr())+ getNumberOfNodesHelper(subTreePtr->getRightChildPtr()); } // end getNumberOfNodesHelper 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::moveValuesUpTree(BinaryNode*subTreePtr) { BinaryNode*leftPtr = subTreePtr->getLeftChildPtr(); BinaryNode*rightPtr = subTreePtr->getRightChildPtr(); int leftHeight =getHeightHelper(leftPtr); int rightHeight =getHeightHelper(rightPtr); if (leftHeight >rightHeight) { subTreePtr->setItem(leftPtr->getItem()); leftPtr = moveValuesUpTree(leftPtr); subTreePtr->setLeftChildPtr(leftPtr); return subTreePtr; } else { if (rightPtr != nullptr) { subTreePtr->setItem(rightPtr->getItem()); rightPtr = moveValuesUpTree(rightPtr); subTreePtr->setRightChildPtr(rightPtr); return subTreePtr; } else { //this was a leaf! // value not important delete subTreePtr; return nullptr; } // end if } // end if } // end moveValuesUpTree template BinaryNode*BinaryNodeTree::removeValue(BinaryNode*subTreePtr, const ItemType target, bool& success) { if (subTreePtr == nullptr)// not found here return nullptr; if(subTreePtr->getItem() == target) // found it { subTreePtr = moveValuesUpTree(subTreePtr); success = true; return subTreePtr; } else { BinaryNode* targetNodePtr = removeValue( subTreePtr->getLeftChildPtr(), target, success); subTreePtr->setLeftChildPtr(targetNodePtr); if (!success) // no need to search right subTree { targetNodePtr = removeValue(subTreePtr->getRightChildPtr(), target, success); subTreePtr->setRightChildPtr(targetNodePtr); } // end if return subTreePtr; } // end if } // end removeValue template BinaryNode*BinaryNodeTree::findNode( BinaryNode*treePtr, const ItemType&target, bool& success)const { if (treePtr == nullptr) //not found here return nullptr; if (treePtr->getItem()== target) // found it { success = true; return treePtr; } else { BinaryNode* targetNodePtr = findNode( treePtr->getLeftChildPtr(), target, success); if (!success) // no need to search right subTree { targetNodePtr = findNode(treePtr->getRightChildPtr(), target,success); } // end if return targetNodePtr; } // end if } // end findNode template BinaryNode*BinaryNodeTree::copyTree( constBinaryNode* treePtr) const { BinaryNode*newTreePtr = nullptr; // Copy tree nodes during apreorder traversal if (treePtr != nullptr) { // Copy node newTreePtr = newBinaryNode(treePtr->getItem(),nullptr,nullptr); newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr())); newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr())); } // end if return newTreePtr; } // end copyTree template voidBinaryNodeTree::destroyTree(BinaryNode*subTreePtr) { if (subTreePtr !=nullptr) { destroyTree(subTreePtr->getLeftChildPtr()); destroyTree(subTreePtr->getRightChildPtr()); delete subTreePtr; } // end if } // end destroyTree template void BinaryNodeTree::preorder(voidvisit(ItemType&), BinaryNode*treePtr) const { if (treePtr != nullptr) { ItemType theItem = treePtr->getItem(); visit(theItem); preorder(visit, treePtr->getLeftChildPtr()); preorder(visit, treePtr->getRightChildPtr()); } // end if } // end preorder template void BinaryNodeTree::inorder(voidvisit(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 template void BinaryNodeTree::postorder(voidvisit(ItemType&), BinaryNode*treePtr) const { if (treePtr != nullptr) { postorder(visit, treePtr->getLeftChildPtr()); postorder(visit, treePtr->getRightChildPtr()); ItemType theItem = treePtr->getItem(); visit(theItem); } // end if } // end postorder template BinaryNodeTree::BinaryNodeTree() :rootPtr(nullptr) { } // end default constructor template BinaryNodeTree::BinaryNodeTree(constItemType& rootItem) { rootPtr = newBinaryNode(rootItem, nullptr, nullptr); } // end constructor template BinaryNodeTree::BinaryNodeTree(constItemType& rootItem, constBinaryNodeTree* leftTreePtr, constBinaryNodeTree* rightTreePtr) { rootPtr = newBinaryNode(rootItem, copyTree(leftTreePtr->rootPtr), copyTree(rightTreePtr->rootPtr)); } // end constructor template BinaryNodeTree::BinaryNodeTree( constBinaryNodeTree& treePtr) { rootPtr =copyTree(treePtr.rootPtr); } // end copy constructor template BinaryNodeTree::~BinaryNodeTree() { destroyTree(rootPtr); } // end destructor template bool BinaryNodeTree::isEmpty() const { return rootPtr ==nullptr; } // end isEmpty template void BinaryNodeTree::clear() { destroyTree(rootPtr); rootPtr = nullptr; } // end clear template bool BinaryNodeTree::add(const ItemType&newData) { BinaryNode*newNodePtr = new BinaryNode(newData); rootPtr =balancedAdd(rootPtr, newNodePtr); return true; } // end add template bool BinaryNodeTree::remove(const ItemType&target) { bool isSuccessful =false; rootPtr =removeValue(rootPtr, target, isSuccessful); return isSuccessful; } // end remove template ItemType BinaryNodeTree::getEntry(constItemType& anEntry) const // throw(NotFoundException) { bool isSuccessful =false; BinaryNode*binaryNodePtr = findNode(rootPtr, anEntry, isSuccessful); if (isSuccessful) return binaryNodePtr->getItem(); else throw NotFoundException(“Entry not found in tree!”); } // end getEntry template void BinaryNodeTree::preorderTraverse(voidvisit(ItemType&)) const { preorder(visit,rootPtr); } // end preorderTraverse template void BinaryNodeTree::inorderTraverse(voidvisit(ItemType&)) const { inorder(visit,rootPtr); } // end inorderTraverse template void BinaryNodeTree::postorderTraverse(voidvisit(ItemType&)) const { postorder(visit,rootPtr); } // end postorderTraverse template BinaryNodeTree&BinaryNodeTree::operator=( constBinaryNodeTree& rightHandSide) { if (!isEmpty()) clear(); this =copyTree(&rightHandSide); return *this; } // end operator= #endif /** @author Scott Johnson * @file BinarySearchTree.h (Listing 16-4) */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #ifndef _BINARY_SEARCH_TREE #define _BINARY_SEARCH_TREE #include “BinaryTreeInterface.h” #include “BinaryNode.h” #include “BinaryNodeTree.h” #include “NotFoundException.h” #include “PrecondViolatedExcep.h” /** Link-based implementation of the ADT binary search tree.*/ template class BinarySearchTree : publicBinaryNodeTree { private: BinaryNode* rootPtr; protected: //———————————————————— // Protected Utility Methods Section: // Recursive helper methods for the public methods. //———————————————————— // Recursively finds where the given node should be placedand // inserts it in a leaf at that point. BinaryNode*insertInorder(BinaryNode* subTreePtr, BinaryNode* newNode); // Removes the given target value from the tree whilemaintaining a // binary search tree. BinaryNode*removeValue(BinaryNode* subTreePtr, const ItemType target, bool& success); // Removes a given node from a tree while maintaining a // binary search tree. BinaryNode*removeNode(BinaryNode* nodePtr); // Removes the leftmost node in the left subtree of the node // pointed to by nodePtr. // Sets inorderSuccessor to the value in this node. // Returns a pointer to the revised subtree. BinaryNode*removeLeftmostNode(BinaryNode* subTreePtr, ItemType& inorderSuccessor); // Returns a pointer to the node containing the given value, // or nullptr if not found. BinaryNode* findNode(BinaryNode*treePtr, const ItemType& target) const; public: //———————————————————— // Constructor and Destructor Section. //———————————————————— BinarySearchTree(); BinarySearchTree(const ItemType& rootItem); BinarySearchTree(const BinarySearchTree&tree); virtual ~BinarySearchTree(); //———————————————————— // Public Methods Section. //———————————————————— bool isEmpty() const; int getHeight() const; int getNumberOfNodes() const; ItemType getRootData() const; // throw(PrecondViolatedExcep) void setRootData(const ItemType& newData) const; // throw(PrecondViolatedExcep) bool add(const ItemType& newEntry); bool remove(const ItemType& anEntry); void clear(); ItemType getEntry(const ItemType& anEntry) const; // throw(NotFoundException) bool contains(const ItemType& anEntry) const; bool iterativeAdd(const ItemType& newEntry); bool equals(const BinaryNode* leftSide, const BinaryNode* rightSide); //———————————————————— // Public Traversals Section. //———————————————————— void preorderTraverse(void visit(ItemType&)) const; void inorderTraverse(void visit(ItemType&)) const; void postorderTraverse(void visit(ItemType&)) const; //———————————————————— // Overloaded Operator Section. //———————————————————— BinarySearchTree& operator=( const BinarySearchTree&rightHandSide); bool operator==( const BinarySearchTree&other); }; // end BinarySearchTree #endif /** @author Frank M. Carrano and Tim Henry. * @file BinaryTreeInterface.h (Listing 15-1) */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #ifndef _BINARY_TREE_INTERFACE #define _BINARY_TREE_INTERFACE template class BinaryTreeInterface { public: virtual bool add(const ItemType& newData) = 0; virtual bool remove(const ItemType& data) = 0; virtual void clear() = 0; virtual ItemType getEntry(const ItemType& anEntry) const =0; 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 /** @author Frank M. Carrano and Tim Henry. * @file NotFoundException.h */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #ifndef _NOT_FOUND_EXCEPTION #define _NOT_FOUND_EXCEPTION #include #include using namespace std; class NotFoundException : public logic_error { public: NotFoundException(const string& message = “”); }; // end NotFoundException #endif /** @author Frank M. Carrano and Tim Henry. * @file PrecondViolatedException.h */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #ifndef _PRECOND_VIOLATED_EXCEPT #define _PRECOND_VIOLATED_EXCEPT #include #include using namespace std; class PrecondViolatedExcep : public logic_error { public: PrecondViolatedExcep(const string& message = “”); }; // end PrecondViolatedExcep #endif /** @author Frank M. Carrano and Tim Henry. * @file NotFoundException.cpp */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #include “NotFoundException.h” NotFoundException::NotFoundException(const string&message) : logic_error(“Precondition Violated Exception: ” + message) { } // end constructor /** @author Frank M. Carrano and Tim Henry. * @file PrecondViolatedExcep.cpp */ // Copyright (c) 2013 __Pearson Education__. All rightsreserved. #include “PrecondViolatedExcep.h” PrecondViolatedExcep::PrecondViolatedExcep(const string&message) : logic_error(“Precondition Violated Exception: ” + message) { } // end constructor // End of implementation file. #include “BinarySearchTree.h” #include #include using namespace std; void display(int& anItem) { cout tree; BinaryNodeTree*tree1Ptr = new BinaryNodeTree (30); BinaryNodeTree*tree2Ptr = new BinaryNodeTree (50); BinaryNodeTree*tree3Ptr = new BinaryNodeTree (40, tree1Ptr,tree2Ptr); BinaryNodeTree*tree4Ptr = new BinaryNodeTree (10); BinaryNodeTree*tree5Ptr = new BinaryNodeTree (20, tree4Ptr,tree3Ptr); BinaryNodeTree*tree6Ptr = new BinaryNodeTree (70); BinaryNodeTree*tree7Ptr = new BinaryNodeTree (60, tree5Ptr,tree6Ptr); cout <<“——————————” << endl; cout <<“——Inorder Traverse——-” << endl; cout <<“——————————” << endl; tree7Ptr->inorderTraverse(display); cout <<“——————————” << endl; cout <<“——Postorder Traverse——-” << endl; cout <<“——————————” << endl; tree7Ptr->postorderTraverse(display); cout <<“——————————” << endl; cout <<“——Preorder Traverse——-” << endl; cout <<“——————————” << endl; tree7Ptr->preorderTraverse(display); return 0; } . . .