Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary...
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 << "\t\t2nd 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 << "\t\t3rd 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;
}
Homework Answers
Below is your code .. bold part is what I have changed
#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> &otherTree)
{
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 << "\t\t2nd 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 << "\t\t3rd 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;
}
void swapSubtrees()
{
swapSubtrees(root);
}
void swapSubtrees(nodeType<elemType> *tree)
{
if(tree!=NULL)
{
nodeType<elemType> *tmp;
swapSubtrees(tree->lLink);
swapSubtrees(tree->rLink);
tmp=tree->lLink;
tree->lLink=tree->rLink;
tree->rLink=tmp;
}
}
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();
treeRoot.swapSubtrees();
cout << endl << "Tree nodes in postorder after swapping: ";
treeRoot.postorderTraversal();
cout << endl;
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;
}
Output
Numbers before Binary Tree: 65 55 22 44 61 19 90 10 78 52
Root value is: 65
2nd Level - Left Tree: 55 2nd Level - Right Tree: 90
3rd Level - Left Tree: 22
3rd Level - Left-Right Tree: 61 3rd Level - Right-Left Tree: 78
4th Level - Left Tree: 19
4th Level - Left-Left-Right Tree: 44
5th Level - Left Tree: 10
5th Level - Left-Left-Rright-Right Tree: 52
Tree nodes in inorder: 10 19 22 44 52 55 61 65 78 90
Tree nodes in preorder: 65 55 22 19 10 44 52 61 90 78
Tree nodes in postorder: 10 19 52 44 22 61 55 78 90 65
Tree nodes in postorder after swapping: 78 90 61 52 44 10
19 22 55 65
Tree Height: 5
Number of Nodes: 10
===========================
Enter a number to Delete: 78
The item to be deleted is not in the tree.
Tree nodes in preorder after delete: 65 90 78 55 61 22 44 52 19
10
===========================
Enter a number to Insert: 78
Tree nodes in preorder after insert: 65 90 78 55 61 22 44 52 19
10 78
===========================
Enter a number to Search: 78
Number was Found in the Tree!
Tree nodes in preorder after Search: 65 90 78 55 61 22 44 52 19
10 78
===========================
--------------------------------
Process exited after 22.01 seconds with return value 0
Press any key to continue . . .
Add Answer to:
Write a function, swapSubtrees, that swaps all of the left and
right subtrees of a binary...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the attached files // BinaryTree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType> *right; }; //Definition of class Binary Tree template <class elemType> class BinaryTree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); BinaryTree(); bool is Empty() const; virtual boot search(const elemType& searchItem) const = 0; virtual void insert(const elemType& insertItem)...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary Tree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType *right; }; //Definition of class Binary Tree template <class elemType> class Binary Tree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); -Binary Tree(): bool is Empty() const; virtual bool search(const elemTypes searchItem) const = 0; virtual void insert(const elemTypek insertItem) =...
C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please...
C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please help me figure out. Thanks. C++ BST implementation (using a struct) Enter the code below, and then compile and run the program. After the program runs successfully, add the following functions: postorder() This function is similar to the inorder() and preorder() functions, but demonstrates postorder tree traversal. displayParentsWithTwo() This function is similar to the displayParents WithOne() function, but displays nodes having only two children....
This is the creatList and printList function #include <iostream> #include <fstream> using namespace std; struct nodeType...
This is the creatList and printList function
#include <iostream>
#include <fstream>
using namespace std;
struct nodeType
{
int info;
nodeType *link;
nodeType *next;
double value;
};
void createList(nodeType*& first, nodeType*& last,
ifstream& inf);
void printList(nodeType* first);
int main()
{
nodeType *first, *last;
int num;
ifstream infile;
infile.open("InputIntegers.txt");
createList(first, last, infile);
printList(first);
infile.close();
system("pause");
return 0;
}
void createList(nodeType*& first, nodeType*& last,
ifstream& infile)
{
int number;...
Hi there, I am working on a binary search tree code in c++. The program must...
Hi there, I am working on a binary search tree code in c++. The program must store and update students' academic records, each node includes the student name, credits attempted, credits earned and GPA. I have made some progress with the code and written most of the functions in the .cpp file (already did the .h file) but i am struggling with what to put in the main and how to put an update part in the insert function. I...
Double linked list implementation of PutItem function. How to fix my code to get desired output b...
Double linked list implementation of PutItem function. How to fix my code to get desired output below: Output: 2 5 8 #ifndef ITEMTYPE_H #define ITEMTYPE_H enum RelationType { LESS, GREATER, EQUAL}; class ItemType { public: ItemType(); void setValue(int newValue); int getValue() const; RelationType ComparedTo(ItemType newItem); private: int value; }; #endif // ITEMTYPE_H // ItemType.cpp #include "ItemType.h" ItemType::ItemType() { value = 0; } void ItemType::setValue(int newValue) { value = newValue; } int ItemType::getValue() const { return value; } RelationType ItemType::ComparedTo(ItemType newItem)...
This project is divided into 3 parts: Part 1. Create a new project and download the arrayList and...
This project is divided into 3 parts: Part 1. Create a new project and download the arrayList and unorderedArrayList templates that are attached. Create a header file for your unorderedSet template and add it to the project. An implementation file will not be needed since the the new class will be a template. Override the definitions of insertAt, insertEnd, and replaceAt in the unorderedSet template definition. Implement the template member functions so that all they do is verify that the...
C++ Help with Test #1 (at bottom) to work properly. May adjust code to work or...
C++ Help with Test #1 (at bottom) to work properly. May adjust code to work or add any additional code. Do not use global variables. #include <iostream> #include <string> using std::endl; using std::cout; using std::cin; using std::string; void pressAnyKeyToContinue() { printf("Press any key to continue\n"); cin.get(); } //This helps with testing, do not modify. bool checkTest(string testName, int whatItShouldBe, int whatItIs) { if (whatItShouldBe == whatItIs) { cout << "Passed " << testName << endl; return true; } else...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {}...
Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {} void insertNode( const NODETYPE &value ) { insertNodeHelper( &rootPtr, value ); } void preOrderTraversal() const { preOrderHelper( rootPtr ); } void inOrderTraversal() const { inOrderHelper( rootPtr ); } private: TreeNode< NODETYPE > *rootPtr; void insertNodeHelper( TreeNode< NODETYPE > **ptr, const NODETYPE &value ) { if ( *ptr == nullptr ) * ptr = new...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the attached files // BinaryTree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType> *right; }; //Definition of class Binary Tree template <class elemType> class BinaryTree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); BinaryTree(); bool is Empty() const; virtual boot search(const elemType& searchItem) const = 0; virtual void insert(const elemType& insertItem)...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary Tree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType *right; }; //Definition of class Binary Tree template <class elemType> class Binary Tree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); -Binary Tree(): bool is Empty() const; virtual bool search(const elemTypes searchItem) const = 0; virtual void insert(const elemTypek insertItem) =...
This is the creatList and printList function
#include <iostream>
#include <fstream>
using namespace std;
struct nodeType
{
int info;
nodeType *link;
nodeType *next;
double value;
};
void createList(nodeType*& first, nodeType*& last,
ifstream& inf);
void printList(nodeType* first);
int main()
{
nodeType *first, *last;
int num;
ifstream infile;
infile.open("InputIntegers.txt");
createList(first, last, infile);
printList(first);
infile.close();
system("pause");
return 0;
}
void createList(nodeType*& first, nodeType*& last,
ifstream& infile)
{
int number;...
Most questions answered within 3 hours.
-
For Bergson the concept of Being contains less reality than does
the concept of Becoming. True...
asked 48 minutes ago -
What is the hydroxide ion concentration, [OH-], in a solution
with a hydronium ion concentration, [H3O+]...
asked 34 minutes ago -
What species is the reducing agent in the following
equation?
Mg(s) + 2HCl (aq) --> MgCl2(aq)...
asked 49 minutes ago -
A 50g ice cube is taken out of a freezer at 0 degrees Celsius
and put...
asked 2 hours ago -
How do ratios help you determine trends? What specific
information do managers look at? Is there...
asked 2 hours ago -
A wavelength of 514 nm is used to find an unknown diffraction
grating. If the separation...
asked 2 hours ago -
Use the central limit theorem to find the mean and standard
error of the mean of...
asked 2 hours ago -
You will be given a file that will contain averages for classes
which are divided into...
asked 2 hours ago -
A Pew Research Center poll surveyed a random sample 850 voters
and asked them if they...
asked 3 hours ago -
Design a class named
NumDays, to
store a value that represents a number of hours and...
asked 3 hours ago -
(R)-2-chloro-(S)-3-bromobutane and
(S)-2-chloro-(S)-3-bromobutane are: A. enantiomers. B.
diastereomers. C. meso compounds. D. the same molecule.
asked 3 hours ago -
1_ What is the Frank-Starling law of the heart? And why the
heart cannot function on...
asked 3 hours ago