Question: This is my code so far... binaryTree.h: #ifndef BINARYTREE_H #define BINARYTREE_H #include using namespace std; //Definition of the Node template struct nodeType { elemType info;
This is my code so far...
binaryTree.h:
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include
using namespace std;
//Definition of the Node
template
struct nodeType
{
elemType info;
nodeType
nodeType
};
//Definition of the class
template
class binaryTreeType
{
public:
const binaryTreeType
(const binaryTreeType
//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 max(elemType x, elemType y) const;
//Function to determine the larger of x and y
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 = nullptr;
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
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
protected:
nodeType
private:
void copyTree(nodeType
nodeType
//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
//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 inorder(nodeType
//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
//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
//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
//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
//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
//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.
};
//Definition of member functions
template
binaryTreeType
{
root = nullptr;
}
template
bool binaryTreeType
{
return (root == nullptr);
}
template
void binaryTreeType
{
inorder(root);
}
template
void binaryTreeType
{
preorder(root);
}
template
void binaryTreeType
{
postorder(root);
}
template
int binaryTreeType
{
return height(root);
}
template
int binaryTreeType
{
return nodeCount(root);
}
template
int binaryTreeType
{
return leavesCount(root);
}
template
void binaryTreeType
(nodeType
nodeType
{
if (otherTreeRoot == nullptr)
copiedTreeRoot = nullptr;
else
{
copiedTreeRoot = new nodeType
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
} //end copyTree
template
void binaryTreeType
(nodeType
{
if (p != nullptr)
{
inorder(p->lLink);
cout info
inorder(p->rLink);
}
}
template
void binaryTreeType
(nodeType
{
if (p != nullptr)
{
cout info
preorder(p->lLink);
preorder(p->rLink);
}
}
template
void binaryTreeType
(nodeType
{
if (p != nullptr)
{
postorder(p->lLink);
postorder(p->rLink);
cout info
}
}
//Overload the assignment operator
template
const binaryTreeType
operator=(const binaryTreeType
{
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;
}
template
void binaryTreeType
{
if (p != nullptr)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = nullptr;
}
}
template
void binaryTreeType
{
destroy(root);
}
//copy constructor
template
binaryTreeType
(const binaryTreeType
{
if (otherTree.root == nullptr) //otherTree is empty
root = nullptr;
else
copyTree(root, otherTree.root);
}
//Destructor
template
binaryTreeType
{
destroy(root);
}
template
int binaryTreeType
(nodeType
{
if (p == nullptr)
return 0;
else
return 1 + max(height(p->lLink), height(p->rLink));
}
template
int binaryTreeType
{
if (x >= y)
return x;
else
return y;
}
template
int binaryTreeType
{
cout
return 0;
}
template
int binaryTreeType
{
cout
return 0;
}
#endif /* BINARYTREE_H */
-------------------------------------------------------------------
binarySearchTree.h:
#ifndef BINARYSEARCHTREE_H #define BINARYSEARCHTREE_H
#include
template
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. void insertPostorder(bSearchTreeType
private: void deleteFromTree(nodeType
};
template
if (root == nullptr) cout
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
template
newNode = new nodeType
if (root == nullptr) root = newNode; else { current = root; while (current != nullptr) { trailCurrent = current;
if (current->info == insertItem) { cout 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
if (root == nullptr) cout
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 info > deleteItem) deleteFromTree(trailCurrent->lLink); else deleteFromTree(trailCurrent->rLink); } else cout
template
if (p == nullptr) cout 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
#endif /* BINARYSEARCHTREE_H */
---------------------------------------------------------------
main.cpp:
#include
#include "binarySearchTree.h" //Line 2
using namespace std; //Line 3
void print(int& x); //Line 4
void update(int& x); //Line 5
int main() //Line 6
{ //Line 7
bSearchTreeType
int num; //Line 9
cout
cin >> num; //Line 11
while (num != -999) //Line 12
{ //Line 13
treeRoot.insert(num); //Line 14
cin >> num; //Line 15
} //Line 16
cout
treeRoot.inorderTraversal(print); //Line 18
cout
cout
treeRoot.inorderTraversal(update); //Line 21
cout
treeRoot.inorderTraversal(print); //Line 23
cout
return 0; //Line 25
} //Line 26
void print(int& x) //Line 27
{ //Line 28
cout
} //Line 30
void update(int& x) //Line 31
{ //Line 32
x = 2 * x; //Line 33
} //Line 34
Fully debug and verify the operation of your abstract and derived classes before proceeding further. Next write a program to perform the following: Build a binary search tree Ti. Perform a postorder traversal of T?, and while performing the traversal, insert the nodes into a second binary search tree T2. Perform a preorder traversal of T2, and while performing the traversal, insert the nodes into a third binary search tree Ts. 1. 2. 3. 4. Perform an inorder traversal of Ts. 5. Output the heights and number of leaves in each of the three binary search trees. Fully debug and verify the operation of your abstract and derived classes before proceeding further. Next write a program to perform the following: Build a binary search tree Ti. Perform a postorder traversal of T?, and while performing the traversal, insert the nodes into a second binary search tree T2. Perform a preorder traversal of T2, and while performing the traversal, insert the nodes into a third binary search tree Ts. 1. 2. 3. 4. Perform an inorder traversal of Ts. 5. Output the heights and number of leaves in each of the three binary search trees
Step by Step Solution
There are 3 Steps involved in it
Detailed Solution Outline for Your Binary Search Tree Program Based on your requirements and the provided code here is a clear plan to help you complete and debug your binaryTreeType and bSearchTreeTy... View full answer
Get step-by-step solutions from verified subject matter experts
Study Help