The followiing code is based on the binary tree letters but it wont compile ----
ID: 3792164 • Letter: T
Question
The followiing code is based on the binary tree letters but it wont compile
----------------------------------------------------------------------------------------------------------------
#ifndef _BINARY_NODE
#define _BINARY_NODE
/** A class of nodes for a link-based binary tree. */
template<class ItemType>
class BinaryNode
{
private:
ItemType item; // Data portion
BinaryNode<ItemType>* leftChildPtr; // Pointer to left child
BinaryNode<ItemType>* rightChildPtr; // Pointer to right child
public:
BinaryNode();
BinaryNode(const ItemType& anItem);
BinaryNode(const ItemType& anItem,
BinaryNode<ItemType>* leftPtr,
BinaryNode<ItemType>* rightPtr);
void setItem(const ItemType& anItem);
ItemType getItem() const;
bool isLeaf() const;
BinaryNode<ItemType>* getLeftChildPtr() const;
BinaryNode<ItemType>* getRightChildPtr() const;
void setLeftChildPtr(BinaryNode<ItemType>* leftPtr);
void setRightChildPtr(BinaryNode<ItemType>* rightPtr);
}; // end BinaryNode
/** @author Frank M. Carrano and Tim Henry
* @file BinaryNode.cpp */
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
#include <cstddef>
template<class ItemType>
BinaryNode<ItemType>::BinaryNode()
: item(nullptr), leftChildPtr(nullptr), rightChildPtr(nullptr)
{
} // end default constructor
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemType& anItem)
: item(anItem), leftChildPtr(nullptr), rightChildPtr(nullptr)
{
} // end constructor
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemType& anItem,
BinaryNode<ItemType>* leftPtr,
BinaryNode<ItemType>* rightPtr)
: item(anItem), leftChildPtr(leftPtr), rightChildPtr(rightPtr)
{
} // end constructor
template<class ItemType>
void BinaryNode<ItemType>::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
template<class ItemType>
ItemType BinaryNode<ItemType>::getItem() const
{
return item;
} // end getItem
template<class ItemType>
bool BinaryNode<ItemType>::isLeaf() const
{
return ((leftChildPtr == nullptr) && (rightChildPtr == nullptr));
}
template<class ItemType>
void BinaryNode<ItemType>::setLeftChildPtr(BinaryNode<ItemType>* leftPtr)
{
leftChildPtr = leftPtr;
} // end setLeftChildPtr
template<class ItemType>
void BinaryNode<ItemType>::setRightChildPtr(BinaryNode<ItemType>* rightPtr)
{
rightChildPtr = rightPtr;
} // end setRightChildPtr
template<class ItemType>
BinaryNode<ItemType>* BinaryNode<ItemType>::getLeftChildPtr() const
{
return leftChildPtr;
} // end getLeftChildPtr
template<class ItemType>
BinaryNode<ItemType>* BinaryNode<ItemType>::getRightChildPtr() const
{
return rightChildPtr;
} // end getRightChildPtr
#endif
/** @author Frank M. Carrano and Tim Henry
* @file BinaryNodeTree.h (Listing 16-3) */
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
#ifndef _BINARY_NODE_TREE
#define _BINARY_NODE_TREE
#include <iostream>
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "PrecondViolatedExcep.h"
#include "NotFoundException.h"
#include <algorithm>
/** ADT binary tree: Link-based implementation. */
template<class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
int getHeightHelper(BinaryNode<ItemType>* subTreePtr) const;
int getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const;
void destroyTree(BinaryNode<ItemType>* subTreePtr); // Recursively deletes all nodes from the tree.
BinaryNode<ItemType>* balancedAdd(BinaryNode<ItemType>* subTreePtr, BinaryNode<ItemType>* newNodePtr);
// Removes the target value from the tree by calling moveValuesUpTree to overwrite value with value from child.
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* 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<ItemType>* moveValuesUpTree(BinaryNode<ItemType>* subTreePtr);
// Recursively searches for target value in the tree by using a preorder traversal.
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr, const ItemType& target, bool& success) const;
// Copies the tree rooted at treePtr and returns a pointer to the copy.
BinaryNode<ItemType>* copyTree(const BinaryNode<ItemType>* treePtr) const;
// Recursive traversal helper methods:
void preorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
void inorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
void postorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
public:
// Constructor and Destructor Section.
BinaryNodeTree();
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem, const BinaryNodeTree<ItemType>* leftTreePtr, const BinaryNodeTree<ItemType>* rightTreePtr);
BinaryNodeTree(const BinaryNodeTree<ItemType>& 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<class ItemType>
int BinaryNodeTree<ItemType>::getHeightHelper(BinaryNode<ItemType>* subTreePtr) const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 + max(getHeightHelper(subTreePtr->getLeftChildPtr()),getHeightHelper(subTreePtr->getRightChildPtr()));
} // end getHeightHelper
template<class ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr()) + getNumberOfNodesHelper(subTreePtr->getRightChildPtr());
} // end getNumberOfNodesHelper
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::balancedAdd(BinaryNode<ItemType>* subTreePtr, BinaryNode<ItemType>* newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else
{
BinaryNode<ItemType>* leftPtr = subTreePtr->getLeftChildPtr();
BinaryNode<ItemType>* 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<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::moveValuesUpTree(BinaryNode<ItemType>* subTreePtr)
{
BinaryNode<ItemType>* leftPtr = subTreePtr->getLeftChildPtr();
BinaryNode<ItemType>* 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<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::removeValue(BinaryNode<ItemType>* 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<ItemType>* 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<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::findNode(
BinaryNode<ItemType>* 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<ItemType>* 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<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::copyTree(
const BinaryNode<ItemType>* treePtr) const
{
BinaryNode<ItemType>* newTreePtr = nullptr;
// Copy tree nodes during a preorder traversal
if (treePtr != nullptr)
{
// Copy node
newTreePtr = new BinaryNode<ItemType>(treePtr->getItem(),nullptr, nullptr);
newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr()));
newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr()));
} // end if
return newTreePtr;
} // end copyTree
template<class ItemType>
void BinaryNodeTree<ItemType>::destroyTree(BinaryNode<ItemType>* subTreePtr)
{
if (subTreePtr != nullptr)
{
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
delete subTreePtr;
} // end if
} // end destroyTree
template<class ItemType>
void BinaryNodeTree<ItemType>::preorder(void visit(ItemType&),
BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
ItemType theItem = treePtr->getItem();
visit(theItem);
preorder(visit, treePtr->getLeftChildPtr());
preorder(visit, treePtr->getRightChildPtr());
} // end if
} // end preorder
template<class ItemType>
void BinaryNodeTree<ItemType>::inorder(void visit(ItemType&),
BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
inorder(visit, treePtr->getLeftChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
inorder(visit, treePtr->getRightChildPtr());
} // end if
} // end inorder
template<class ItemType>
void BinaryNodeTree<ItemType>::postorder(void visit(ItemType&),
BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
postorder(visit, treePtr->getLeftChildPtr());
postorder(visit, treePtr->getRightChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
} // end if
} // end postorder
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree() : rootPtr(nullptr)
{
} // end default constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem)
{
rootPtr = new BinaryNode<ItemType>(rootItem, nullptr, nullptr);
} // end constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem,
const BinaryNodeTree<ItemType>* leftTreePtr,
const BinaryNodeTree<ItemType>* rightTreePtr)
{
rootPtr = new BinaryNode<ItemType>(rootItem,
copyTree(leftTreePtr->rootPtr),
copyTree(rightTreePtr->rootPtr));
} // end constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(
const BinaryNodeTree<ItemType>& treePtr)
{
rootPtr = copyTree(treePtr.rootPtr);
} // end copy constructor
template<class ItemType>
BinaryNodeTree<ItemType>::~BinaryNodeTree()
{
destroyTree(rootPtr);
} // end destructor
template<class ItemType>
bool BinaryNodeTree<ItemType>::isEmpty() const
{
return rootPtr == nullptr;
} // end isEmpty
template<class ItemType>
void BinaryNodeTree<ItemType>::clear()
{
destroyTree(rootPtr);
rootPtr = nullptr;
} // end clear
template<class ItemType>
bool BinaryNodeTree<ItemType>::add(const ItemType& newData)
{
BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newData);
rootPtr = balancedAdd(rootPtr, newNodePtr);
return true;
} // end add
template<class ItemType>
bool BinaryNodeTree<ItemType>::remove(const ItemType& target)
{
bool isSuccessful = false;
rootPtr = removeValue(rootPtr, target, isSuccessful);
return isSuccessful;
} // end remove
template<class ItemType>
ItemType BinaryNodeTree<ItemType>::getEntry(const ItemType& anEntry) const
// throw(NotFoundException)
{
bool isSuccessful = false;
BinaryNode<ItemType>* binaryNodePtr = findNode(rootPtr,
anEntry, isSuccessful);
if (isSuccessful)
return binaryNodePtr->getItem();
else
throw NotFoundException("Entry not found in tree!");
} // end getEntry
template<class ItemType>
void BinaryNodeTree<ItemType>::preorderTraverse(void visit(ItemType&)) const
{
preorder(visit, rootPtr);
} // end preorderTraverse
template<class ItemType>
void BinaryNodeTree<ItemType>::inorderTraverse(void visit(ItemType&)) const
{
inorder(visit, rootPtr);
} // end inorderTraverse
template<class ItemType>
void BinaryNodeTree<ItemType>::postorderTraverse(void visit(ItemType&)) const
{
postorder(visit, rootPtr);
} // end postorderTraverse
template<class ItemType>
BinaryNodeTree<ItemType>& BinaryNodeTree<ItemType>::operator=(
const BinaryNodeTree<ItemType>& 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 rights reserved.
#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 ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Recursively finds where the given node should be placed and
// inserts it in a leaf at that point.
BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
BinaryNode<ItemType>* newNode);
// Removes the given target value from the tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,
const ItemType target,
bool& success);
// Removes a given node from a tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* 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<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr,
ItemType& inorderSuccessor);
// Returns a pointer to the node containing the given value,
// or nullptr if not found.
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
const ItemType& target) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& 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<ItemType>* leftSide,
const BinaryNode<ItemType>* 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<ItemType>& operator=(
const BinarySearchTree<ItemType>& rightHandSide);
bool operator==(
const BinarySearchTree<ItemType>& other);
}; // end BinarySearchTree
#endif
/** @author Frank M. Carrano and Tim Henry.
* @file BinaryTreeInterface.h (Listing 15-1) */
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
#ifndef _BINARY_TREE_INTERFACE
#define _BINARY_TREE_INTERFACE
template<class ItemType>
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 rights reserved.
#ifndef _NOT_FOUND_EXCEPTION
#define _NOT_FOUND_EXCEPTION
#include <stdexcept>
#include <string>
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 rights reserved.
#ifndef _PRECOND_VIOLATED_EXCEPT
#define _PRECOND_VIOLATED_EXCEPT
#include <stdexcept>
#include <string>
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 rights reserved.
#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 rights reserved.
#include "PrecondViolatedExcep.h"
PrecondViolatedExcep::PrecondViolatedExcep(const string& message)
: logic_error("Precondition Violated Exception: " + message)
{
} // end constructor
// End of implementation file.
#include "BinarySearchTree.h"
#include <string>
#include <iostream>
using namespace std;
void display(int& anItem)
{
cout << "Displaying item - " << anItem << endl;
} // end display
int main()
{
BinaryNodeTree<int> tree;
BinaryNodeTree<int>* tree1Ptr = new BinaryNodeTree <int> (30);
BinaryNodeTree<int>* tree2Ptr = new BinaryNodeTree <int> (50);
BinaryNodeTree<int>* tree3Ptr = new BinaryNodeTree <int> (40, tree1Ptr, tree2Ptr);
BinaryNodeTree<int>* tree4Ptr = new BinaryNodeTree <int> (10);
BinaryNodeTree<int>* tree5Ptr = new BinaryNodeTree <int> (20, tree4Ptr, tree3Ptr);
BinaryNodeTree<int>* tree6Ptr = new BinaryNodeTree <int> (70);
BinaryNodeTree<int>* tree7Ptr = new BinaryNodeTree <int> (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;
}
Explanation / Answer
You have not written your program is for what!! Code for header file containing the class BinaryNode for a link-based implementation of the ADT binary tree and link-based implementation of the class BinaryNodeTree is error free. Try following codes for traversal of
To place pointer to node on stack before traversing the nodes left subtree
nodeStack.push (curPtr)
To check if stack is it will backtrack from the empty subtree and visit the node at the top of the stack
curPtr = curPtr->getRightChildPtr ()} //to traverse the right subtree of the noxe just visited