Write a function, swapSubtrees, that swaps all of the left and right subtrees of
ID: 3713101 • 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.
#include <iostream>
using namespace std;
//Definition of the Node
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
//Overload the assignment operator.
const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&)
{
if (this != &otherTree) //avoid self-copy
{
if (root != nullptr) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == nullptr) //otherTree is empty
root = nullptr;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
//Function to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
bool isEmpty() const
{
return (root == nullptr);
}
//Function to do an inorder traversal of the binary tree.
//Postcondition: Nodes are printed in inorder sequence.
void inorderTraversal() const
{
inorder(root);
}
//Function to do a preorder traversal of the binary tree.
//Postcondition: Nodes are printed in preorder sequence.
void preorderTraversal() const
{
preorder(root);
}
//Function to do a postorder traversal of the binary tree.
//Postcondition: Nodes are printed in postorder sequence.
void postorderTraversal() const
{
postorder(root);
}
//Function to determine the height of a binary tree.
//Postcondition: Returns the height of the binary tree.
int treeHeight() const
{
return height(root);
}
//Function to determine the number of nodes in a
//binary tree.
//Postcondition: Returns the number of nodes in the
// binary tree.
int treeNodeCount() const
{
return nodeCount(root);
}
//Function to determine the number of leaves in a
//binary tree.
//Postcondition: Returns the number of leaves in the
// binary tree.
int treeLeavesCount() const
{
return leavesCount(root);
}
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by each node
// is deallocated.
// root = nullptr;
void destroyTree()
{
destroy(root);
}
//Function to determine if searchItem is in the binary
//tree.
//Postcondition: Returns true if searchItem is found in
// the binary tree; otherwise, returns
// false.
bool search(const elemType& searchItem) const
{
nodeType<elemType> *current;
bool found = false;
if (root == nullptr)
cout << "Cannot search an empty tree." << endl;
else
{
current = root;
while (current != nullptr && !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
//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.
void 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
trailCurrent = NULL;
newNode = new nodeType<elemType>;
newNode->info = insertItem;
newNode->lLink = nullptr;
newNode->rLink = nullptr;
if (root == nullptr)
root = newNode;
else
{
current = root;
while (current != nullptr)
{
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
//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.
void deleteNode(const elemType& deleteItem)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
bool found = false;
if (root == nullptr)
cout << "Cannot delete from an empty tree."
<< endl;
else
{
current = root;
trailCurrent = root;
while (current != nullptr && !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 == nullptr)
cout << "The item to be deleted is not in the tree."
<< endl;
else if (found)
{
if (current == root)
deleteFromTree(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
//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.
void 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 == nullptr)
cout << "Error: The node to be deleted does not exist."
<< endl;
else if (p->lLink == nullptr && p->rLink == nullptr)
{
temp = p;
p = nullptr;
delete temp;
}
else if (p->lLink == nullptr)
{
temp = p;
p = temp->rLink;
delete temp;
}
else if (p->rLink == nullptr)
{
temp = p;
p = temp->lLink;
delete temp;
}
else
{
current = p->lLink;
trailCurrent = nullptr;
while (current->rLink != nullptr)
{
trailCurrent = current;
current = current->rLink;
}//end while
p->info = current->info;
if (trailCurrent == nullptr) //current did not move;
//current == p->lLink; adjust p
p->lLink = current->lLink;
else
trailCurrent->rLink = current->lLink;
delete current;
}//end else
} //end deleteFromTree
//Copy constructor
binaryTreeType(const binaryTreeType<elemType>& otherTree)
{
if (otherTree.root == nullptr) //otherTree is empty
root = nullptr;
else
copyTree(root, otherTree.root);
}
//Default constructor
binaryTreeType()
{
root = nullptr;
}
//Destructor
~binaryTreeType()
{
destroy(root);
}
void displayRoot()
{
cout << "Root value is: " << root->info << endl;
}
void displayL2()
{
cout << "2nd Level - Left Tree: " << root->lLink->info;
cout << " 2nd Level - Right Tree: " << root->rLink->info << endl;
}
void displayL3()
{
cout << "3rd Level - Left Tree: " << root->lLink->lLink->info << endl;
cout << "3rd Level - Left-Right Tree: " << root->lLink->rLink->info;
cout << " 3rd Level - Right-Left Tree: " << root->rLink->lLink->info << endl;
}
void displayL4()
{
cout << "4th Level - Left Tree: " << root->lLink->lLink->lLink->info << endl;
cout << "4th Level - Left-Left-Right Tree: " << root->lLink->lLink->rLink->info << endl;
}
void displayL5()
{
cout << "5th Level - Left Tree: " << root->lLink->lLink->lLink->lLink->info << endl;
cout << "5th Level - Left-Left-Rright-Right Tree: " << root->lLink->lLink->rLink->rLink->info << endl;
}
protected:
nodeType<elemType> *root;
private:
//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 copyTree(nodeType<elemType>* &copiedTreeRoot, nodeType<elemType>* otherTreeRoot)
{
if (otherTreeRoot == nullptr)
copiedTreeRoot = nullptr;
else
{
copiedTreeRoot = new nodeType<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
} //end copyTree
//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 = nullptr;
void destroy(nodeType<elemType>* &p)
{
if (p != nullptr)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = nullptr;
}
}
//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 inorder(nodeType<elemType> *p) const
{
if (p != nullptr)
{
inorder(p->lLink);
cout << p->info << " ";
inorder(p->rLink);
}
}
//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 preorder(nodeType<elemType> *p) const
{
if (p != nullptr)
{
cout << p->info << " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
//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.
void postorder(nodeType<elemType> *p) const
{
if (p != nullptr)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info << " ";
}
}
//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 height(nodeType<elemType> *p) const
{
if (p == nullptr)
return 0;
else
return 1 + max(height(p->lLink), height(p->rLink));
}
//Function to determine the larger of x and y.
//Postcondition: Returns the larger of x and y.
int max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
//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 nodeCount(nodeType<elemType> *p) const
{
if (p == nullptr)
return 0;
else
return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}
//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.
int leavesCount(nodeType<elemType> *p) const
{
cout << "Write the definition of the function leavesCount." << endl;
return 0;
}
};
int main()
{
binaryTreeType<int> treeRoot;
int num;
//cout << "Enter integers ending with -999" << endl;
//cin >> num;
//while (num != -999)
//{
// treeRoot.insert(num);
// cin >> num;
//}
//Data: 65 55 22 44 61 19 90 10 78 52 -999
cout << "Numbers before Binary Tree: "
<< 65 << " " << 55 << " " << 22 << " " << 44
<< " " << 61 << " " << 19 << " " << 90 << " " << 10
<< " " << 78 << " " << 52 << endl;
treeRoot.insert(65);
treeRoot.insert(55);
treeRoot.insert(22);
treeRoot.insert(44);
treeRoot.insert(61);
treeRoot.insert(19);
treeRoot.insert(90);
treeRoot.insert(10);
treeRoot.insert(78);
treeRoot.insert(52);
cout << endl;
treeRoot.displayRoot();
cout << endl;
treeRoot.displayL2();
cout << endl;
treeRoot.displayL3();
cout << endl;
treeRoot.displayL4();
cout << endl;
treeRoot.displayL5();
cout << endl << "Tree nodes in inorder: ";
treeRoot.inorderTraversal();
cout << endl << "Tree nodes in preorder: ";
treeRoot.preorderTraversal();
cout << endl << "Tree nodes in postorder: ";
treeRoot.postorderTraversal();
cout << endl;
cout << "Tree Height: " << treeRoot.treeHeight() << endl;
cout << "Number of Nodes: " << treeRoot.treeNodeCount() << endl;
cout << endl;
cout << endl << "===========================" << endl;
int val = 0;
cout << "Enter a number to Delete: ";
cin >> val;
treeRoot.deleteNode(val);
cout << endl << "Tree nodes in preorder after delete: ";
treeRoot.preorderTraversal();
cout << endl << "===========================" << endl;
cout << "Enter a number to Insert: ";
cin >> val;
treeRoot.insert(val);
cout << endl << "Tree nodes in preorder after insert: ";
treeRoot.preorderTraversal();
cout << endl << "===========================" << endl;
cout << "Enter a number to Search: ";
cin >> val;
if (treeRoot.search(val))
cout << "Number was Found in the Tree!" << endl;
cout << endl << "Tree nodes in preorder after Search: ";
treeRoot.preorderTraversal();
cout << endl << "===========================" << endl;
return 0;
}
Explanation / Answer
#include <iostream>
using namespace std;
// Class binaryTreeType
//Definition of the node
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&);
//overload assignment operator
bool isEmpty() const;
//checks if tree is empty
//postcondition: returns T if empty, F otherwise
void inorderTraversal()const;
//does inorder traversal
//postcondition: nodes printed in inorder sequence
void preorderTraversal() const;
//does preoder traversal of tree
//postcondition: nodes printed in preorder sequence
void postorderTraversal() const;
//does postorder traversal
//postcondition: nodes printed in postorder sequence
int treeHeight() const;
//determines height of tree
//postcondition:returns height of tree
int treeNodeCount()const;
//counts nodes in the tree
//postcondition: returns number of nodes
int treeLeavesCount()const;
//counts leaves in the tree
//postcondition: returns number of leaves
void destroyTree();
//destroys tree
// postcondition: deallocates memory space of each node, root = NULL
virtual bool search(const elemType& searchItem) const = 0;
//determines if searchItem is in tree
//postcondition: returns true if searchItem found, fals otherwise
virtual void insert(const elemType& insertItem) = 0;
//inserts insertItem into tree
//postcondition: if no node has same info as insertItem, a node with
// the info insertItem is created and inserted into tree
virtual void deleteNode(const elemType& deleteItem) = 0;
//deletes deletItem from tree
//postcondition: if a node with same info as deleteItem is found it is
//deleted from the tree. If tree is empty or delteItem not in tree
//a message is printed
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//copy constructor
binaryTreeType();
//default constructor
~binaryTreeType();
//Destructor
protected:
nodeType<elemType> *root;
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//copies the tree to which otherTreeRoot points
//postcondition:pointer copiedTreeRoot points to the root of the copied
//tree
void destroy(nodeType<elemType>* &p);
//destroys the tree to which p points
//postcondition: memory occupied by tree to which p points is
//deallocated. P = NULL;
void inorder(nodeType<elemType> *p)const;
//in order traversal of tree to which p points
//postcondition: nodes of tree to which p points printed in inorder
//sequence
void preorder(nodeType<elemType> *p)const;
//pre order traversal of tree to which p points
//postcondition: nodes of tree to which p points printed in preorder
//sequence
void postorder(nodeType<elemType> *p)const;
//post order traversal of tree to which p points
//postcondition: nodes of tree to which p points printed in postorder
//sequence
int height(nodeType<elemType> *p)const;
//determines height of tree to which p points
//postcondition: retursn height of tree to which p points
int max(int x, int y)const;
//determines the larger of x and y
//postcondition: returns larger of z and y
int nodeCount(nodeType<elemType> *p)const;
//counts number of nodes in tree to which p points
//postcondition: returns number of nodes in tree to which p points
int leavesCount(nodeType<elemType> *p)const;
//counts number of leaves in tree to which p points
//postcondition: returns number of leaves in tree to which p points
/*
void swapSubTrees();
//swaps all of the left and right subtrees of binary tree
*/
};
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;
}
//nodeCount and leavesCount are left out for me to code if I need them
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 tree not empty
destroy(root); //destroy the tree
if(otherTree.root == NULL) //if tree not empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
/*
//here is my swapSubTrees function to be written and tested
//I think my algorithm below will work if node type is a pointer
template<class elemType>
void binaryTreeType<elemType>::swapSubTrees()
{
nodeType Temp; = root->lLink;
root->llink = root->rLink;
root->rlink = Temp;
delete Temp; // do I need to do this?
}
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.