Write a function, swapSubtrees, that swaps all of the left and right subtrees of
ID: 666144 • Letter: W
Question
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function.
I DID THE JOB BUT I HAVE AN ERROR MESSAGE, CAN SOMEONE HELP ME RUN THIS MY PROGRAM.JUST COPY AND PAST IT IN YOUR EDITOR AND SEE THE PROBLEM.
2 IntelliSense: object of abstract class type "binaryTreeType<int>" is not allowed:
function "binaryTreeType<elemType>::search [with elemType=int]" is a pure virtual function
function "binaryTreeType<elemType>::insert [with elemType=int]" is a pure virtual function
function "binaryTreeType<elemType>::deleteNode [with elemType=int]" is a pure virtual function c:UsersLEMANOUDocumentsVisual Studio 2012ProjectsBinaryTreeBinaryTreeSource.cpp 558 25 BinaryTree
#include<iostream>
using namespace std;
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
//Function to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
//otherwise, returns false.
void inorderTraversal() const;
//Function to do an inorder traversal of the binary tree.
//Postcondition: Nodes are printed in inorder sequence.
void preorderTraversal() const;
//Function to do a preorder traversal of the binary tree.
//Postcondition: Nodes are printed in preorder sequence.
void postorderTraversal() const;
//Function to do a postorder traversal of the binary tree.
//Postcondition: Nodes are printed in postorder sequence.
int treeHeight() const;
//Function to determine the height of a binary tree.
//Postcondition: Returns the height of the binary tree.
int treeNodeCount() const;
//Function to determine the number of nodes in a
//binary tree.
//Postcondition: Returns the number of nodes in the
//binary tree.
int treeLeavesCount() const;
//Function to determine the number of leaves in a
//binary tree.
//Postcondition: Returns the number of leaves in the
//binary tree.
void destroyTree();
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by each node
//is deallocated.
//root = NULL;
virtual bool search(const elemType& searchItem) const = 0;
//Function to determine if searchItem is in the binary
//tree.
//Postcondition: Returns true if searchItem is found in
//the binary tree; otherwise, returns
//false.
virtual void insert(const elemType& insertItem) = 0;
//Function to insert insertItem in the binary tree.
//Postcondition: If there is no node in the binary tree
//that has the same info as insertItem, a
//node with the info insertItem is created
//and inserted in the binary search tree.
virtual void deleteNode(const elemType& deleteItem) = 0;
//Function to delete deleteItem from the binary tree.
//Postcondition: If a node with the same info as
//deleteItem is found, it is deleted from
//the binary tree.
//If the binary tree is empty or
//deleteItem is not in the binary tree,
//an appropriate message is printed.
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//Copy constructor
binaryTreeType();
//Default constructor
~ binaryTreeType();
//Destructor
void swapSubtrees() ;
protected:
nodeType<elemType> *root;
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//Makes a copy of the binary tree to which
//otherTreeRoot points.
//Postcondition: The pointer copiedTreeRoot points to
//the root of the copied binary tree.
void destroy(nodeType<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: Memory space occupied by each node, in
//the binary tree to which p points, is
//deallocated.
//p = NULL;
void inorder(nodeType<elemType> *p) const;
//Function to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
//points, are printed in inorder sequence.
void preorder(nodeType<elemType> *p) const;
//Function to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
//points, are printed in preorder
//sequence.
void postorder(nodeType<elemType> *p) const;
//Function to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
//points, are printed in postorder
//sequence.
int height(nodeType<elemType> *p) const;
//Function to determine the height of the binary tree
//to which p points.
//Postcondition: Height of the binary tree to which
//p points is returned.
int max(int x, int y) const;
//Function to determine the larger of x and y.
//Postcondition: Returns the larger of x and y.
int nodeCount(nodeType<elemType> *p) const;
//Function to determine the number of nodes in
//the binary tree to which p points.
//Postcondition: The number of nodes in the binary
//tree to which p points is returned.
int leavesCount(nodeType<elemType> *p) const;
//Function to determine the number of leaves in
//the binary tree to which p points.
//Postcondition: The number of leaves in the binary
//tree to which p points is returned.
};
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::inorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
inorder(p->lLink);
cout << p->info << " ";
inorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::preorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::postorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info << " ";
}
}
template<class elemType>
int binaryTreeType<elemType>::height
(nodeType<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->lLink), height(p->rLink));
}
template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new nodeType<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
} //end copyTree
template <class elemType>
void binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
if (p != NULL)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}
//Destructor
template <class elemType>
binaryTreeType<elemType>:: ~ binaryTreeType()
{
destroy(root);
}
//Overload the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL)
//if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
template<class elemType>
void binaryTreeType<elemType>::swapSubtrees()
{
if(root !=NULL)
{
nodeType<elemType> *tmp;
swapSubtrees(root->left);
swapSubtrees(root->right);
tmp=root->left;
tree->root=tree->right;
root->right=tmp;
}
}
//CLASS bSearchTreeType//
template <class elemType>
class bSearchTreeType:
public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem) const;
//Function to determine if searchItem is in the binary
//search tree.
//Postcondition: Returns true if searchItem is found in
//the binary search tree; otherwise,
//returns false.
void insert(const elemType& insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If there is no node in the binary search
//tree that has the same info as
//insertItem, a node with the info
//insertItem is created and inserted in the
//binary search tree.
void deleteNode(const elemType& deleteItem);
//Function to delete deleteItem from the binary search tree.
//Postcondition: If a node with the same info as deleteItem
//is found, it is deleted from the binary
//search tree.
//If the binary tree is empty or deleteItem
//is not in the binary tree, an appropriate
//message is printed.
private:
void deleteFromTree(nodeType<elemType>* &p);
//Function to delete the node to which p points is
//deleted from the binary search tree.
//Postcondition: The node to which p points is deleted
//from the binary search tree.
};
template <class elemType>
bool bSearchTreeType<elemType>::search
(const elemType& searchItem) const
{
nodeType<elemType> *current;
bool found = false;
if (binaryTreeType<elemType>::root == NULL)
cout << "Cannot search an empty tree." << endl;
else
{
current = binaryTreeType<elemType>::root;
while (current != NULL && !found)
{
if (current->info == searchItem)
found = true;
else if (current->info > searchItem)
current = current->lLink;
else
current = current->rLink;
}//end while
}//end else
return found;
}//end search
template <class elemType>
void bSearchTreeType<elemType>::insert
(const elemType& insertItem)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *newNode; //pointer to create the node
newNode = new nodeType<elemType>;
newNode->info = insertItem;
newNode->lLink = NULL;
newNode->rLink = NULL;
if (binaryTreeType<elemType>::root == NULL)
binaryTreeType<elemType>::root = newNode;
else
{
current = binaryTreeType<elemType>::root;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cout << "The item to be inserted is already ";
cout << "in the tree -- duplicates are not "
<< "allowed." << endl;
return;
}
else if (current->info > insertItem)
current = current->lLink;
else
current = current->rLink;
}//end while
if (trailCurrent->info > insertItem)
trailCurrent->lLink = newNode;
else
trailCurrent->rLink = newNode;
}
}//end insert
template <class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(nodeType<elemType>* &p)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *temp;
//pointer to delete the node
if (p == NULL)
cout << "Error: The node to be deleted is NULL."
<< endl;
else if (p->lLink == NULL && p->rLink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if (p->lLink == NULL)
{
temp = p;
p = temp->rLink;
delete temp;
}
else if (p->rLink == NULL)
{
temp = p;
p = temp->lLink;
delete temp;
}
else
{
current = p->lLink;
trailCurrent = NULL;
while (current->rLink != NULL)
{
trailCurrent = current;
current = current->rLink;
}//end while
p->info = current->info;
if (trailCurrent == NULL) //current did not move;
//current == p->lLink; adjust p
p->lLink = current->lLink;
else
trailCurrent->rLink = current->lLink;
delete current;
}//end else
} //end deleteFromTree
template <class elemType>
void bSearchTreeType<elemType>::deleteNode
(const elemType& deleteItem)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
bool found = false;
if (binaryTreeType<elemType>::root == NULL)
cout << "Cannot delete from an empty tree."
<< endl;
else
{
current = binaryTreeType<elemType>::root;
trailCurrent = binaryTreeType<elemType>::root;
while (current != NULL && !found)
{
if (current->info == deleteItem)
found = true;
else
{
trailCurrent = current;
if (current->info > deleteItem)
current = current->lLink;
else
current = current->rLink;
}
}//end while
if (current == NULL)
cout << "The item to be deleted is not in the tree."
<< endl;
else if (found)
{
if (current == binaryTreeType<elemType>::root)
deleteFromTree(binaryTreeType<elemType>::root);
else if (trailCurrent->info > deleteItem)
deleteFromTree(trailCurrent->lLink);
else
deleteFromTree(trailCurrent->rLink);
}
else
cout << "The item to be deleted is not in the tree."
<< endl;
}
} //end deleteNode
//Main Program//
int main()
{
binaryTreeType<int> btt;
int ch,ele;
do
{
cout<<" 1----INSERT A NODE IN A BINARY TREE.";
cout<<" 2----PRE-ORDER TRAVERSAL.";
cout<<" 3----IN-ORDER TRAVERSAL.";
cout<<" 4----POST-ORDER TRAVERSAL.";
cout<<" 5----SWAP SUBTREES.";
cout<<" 6----EXIT.";
cout<<" ENTER CHOICE: ";
cin>>ch;
switch(ch)
{
case 1:
cout<<" ENTER THE ELEMENT: ";
cin>>ele;
btt.insert(ele);
break;
case 2:
cout<<" ****PRE-ORDER TRAVERSAL OF A TREE**** ";
btt.preorderTraversal();
cout<<endl;
break;
case 3:
cout<<" ****IN-ORDER TRAVERSAL OF A TREE**** ";
btt.inorderTraversal();
cout<<endl;
break;
case 4:
cout<<" ****POST-ORDER TRAVERSAL OF A TREE**** ";
btt.postorderTraversal();
cout<<endl;
break;
case 5:
btt.swapSubtrees();
cout<<" swapping is done successfully ";
break;
case 6:
exit(0);
}
system("pause");
return 0 ;
}while(ch!=6);
}
Explanation / Answer
Hi,
You need to redefine ALL the pure virtual functions in the derived class, otherwise the class is incomplete - that is still abstract, because all the functions are inherited.
Hope that helps..HAPPY ANSWERING!!!!!!!!!!!!!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.