In C++ Binary Search Trees Description In this lab your goal is to implement sta
ID: 3701310 • Letter: I
Question
In C++
Binary Search Trees Description In this lab your goal is to implement standard operations of binary search trees, inchuding insert and delete. See section 12.3 in the textbook. There 're millions of ways of implementing delete operation, but you must follow eractly the same algorithm in the tertbook. In this assignment the keys are integers. Your code will be tested for exampks consisting of distinct keys. In the input, each starts with 'e', i', "d', 'oin', opre', or 'opost'. For each line, you will have to do the folloming. eikey): Insert (key) into the BST. For example, i2 implies Insert key 2 into the BST. d(key): delete (key) from the BST-For example, d2 implies .delete key 2 from the BST." Do nothing if the BST doesn't have the key. eopre: output all keys via preorder walk. opost: output all keys via postorder walk. oin: output all keys via inoeder walk. e: finish your program. Example input and output The following example shows an execution of the program in interactive mode. See the input files and output files under the testfiles folder for examples where input and output are separated. 13 i1 i5 d7 opre opostExplanation / Answer
// File Name: BSTMenuStringFile.cpp
#include<iostream>
#include <sstream> // For stringstream to convert string to integer
#include <cstdlib> // For exit() function
#include<fstream> // For reading file
#include <string>
#include<stdio.h>
using namespace std;
// Structure definition for binary tree
struct BinaryTreeNode
{
// Structure member to store key, left child and right child
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
};// End of structure
/* Function to returns the node having minimum value
* Parameters:
* *tnode: pointer to root node
*/
BinaryTreeNode* FindMin(BinaryTreeNode *tnode)
{
// Checks if tree is empty
if(tnode == NULL)
//There is no element in the tree
return NULL;
// Go to the left sub tree to find the min element
if(tnode -> left)
// Recursively call the function to find the minimum
return FindMin(tnode -> left);
else
return tnode;
}// End of function
/* Function to insert a node
* Parameters:
* *tnode: pointer to root node
* value: value to insert in binary tree
*/
BinaryTreeNode *Insert(BinaryTreeNode *tnode, int value)
{
// Checks if tree is empty
if(tnode == NULL)
{
// Creates a temporary pointer
BinaryTreeNode *temp;
// Allocates memory
temp = new BinaryTreeNode;
// Assigns value
temp -> value = value;
// Initializes left and right node to null
temp -> left = temp -> right = NULL;
// Returns the node
return temp;
}// End of if
// Checks if the entered value is greater than the current node value
if(value > tnode -> value)
{
// Insert the node at right
tnode -> right = Insert(tnode -> right, value);
}// End of if
// Checks if the entered value is less than the current node value
else if(value < tnode -> value)
{
// Insert the node at left
tnode -> left = Insert(tnode -> left, value);
}// End of else if
// else there is nothing to do as the data is already in the tree.
return tnode;
}// End of function
/* Function to delete a node from tree
* Parameters:
* *tnode: pointer to root node
* value: value to delete from binary tree
*/
BinaryTreeNode * Delete(BinaryTreeNode *tnode, int value)
{
// Creates a temporary pointer
BinaryTreeNode *temp;
// Checks if tree is empty displays message
if(tnode == NULL)
{
cout<<" Element Not Found";
}// End of if
// Checks if the entered value is less than the current node value
else if(value < tnode -> value)
{
// Recursively calls the function with left child
tnode -> left = Delete(tnode -> left, value);
}// End of else if condition
// Checks if the entered value is greater than the current node value
else if(value > tnode -> value)
{
// Recursively calls the function with right child
tnode -> right = Delete(tnode -> right, value);
}// End of else
// Otherwise
else
{
// Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree
if(tnode -> right && tnode -> left)
{
// Here we will replace with minimum element in the right sub tree
temp = FindMin(tnode -> right);
tnode -> value = temp -> value;
// As we replaced it with some other node, we have to delete that node
tnode -> right = Delete(tnode -> right, temp -> value);
}// End of if condition
// Otherwise
else
{
// If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child
temp = tnode;
if(tnode -> left == NULL)
// Temporary node is pointing to right
tnode = tnode -> right;
else if(tnode -> right == NULL)
// Temporary node is pointing to left
tnode = tnode -> left;
// Delete temporary node
free(temp);
}// End of inner else
}// End of outer else
// Returns the node
return tnode;
}// End of function
/* Function for Inorder traversal
* Parameters:
* *tnode: pointer to root node
* result: integer array to store the order of traversal number
* returns how many number traversed
*/
int Inorder(BinaryTreeNode *tnode, int result [])
{
// Static counter for count numbers
static int c = 0;
// Checks if tree is empty
if(tnode == NULL)
return c;
// Recursively calls the left child node
Inorder(tnode -> left, result);
// Stores the value at c index position of result array
result[c] = tnode -> value;
// Increase the counter by one
c++;
// Recursively calls the right child node
Inorder(tnode -> right, result);
// Reset the counter position to one
c = 1;
}//End of function
/* Function for Pre order traversal
* Parameters:
* *tnode: pointer to root node
* result: integer array to store the order of traversal number
* returns how many number traversed
*/
int Preorder(BinaryTreeNode *tnode, int result [])
{
// Static counter for count numbers
static int c = 0;
// Checks if tree is empty
if(tnode == NULL)
return c;
// Stores the value at c index position of result array
result[c] = tnode -> value;
// Increase the counter by one
c++;
// Recursively calls the left child node
Preorder(tnode -> left, result);
// Recursively calls the right child node
Preorder(tnode -> right, result);
// Reset the counter position to one
c = 1;
}// End of function
/* Function for Post order traversal
* Parameters:
* *tnode: pointer to root node
* result: integer array to store the order of traversal number
* returns how many number traversed
*/
int Postorder(BinaryTreeNode *tnode, int result [])
{
// Static counter for count numbers
static int c = 0;
// Checks if tree is empty
if(tnode == NULL)
return c;
// Recursively calls the left child node
Postorder(tnode -> left, result);
// Recursively calls the right child node
Postorder(tnode -> right, result);
// Stores the value at c index position of result array
result[c] = tnode -> value;
// Increase the counter by one
c++;
// Reset the counter position to one
c = 1;
}// End of function
// Function to read the instructions from file and return number of instructions
int readFile(string instruction[])
{
// ifstream object to read
ifstream rFile;
// Counter for number of instructions
int counter = 0;
// Opens the file for reading
rFile.open("BSTStringData.txt");
// Check that file can be opened or not
// is_open() function returns true if a file is open and associated with this stream object.
// Otherwise returns false.
if(!rFile.is_open())
{
// Displays error message
cout<<" Error: Unable to open the file!";
exit(0);
}// End of if condition
// Loops end of file
while(!rFile.eof())
{
// Read the instruction and store it in string array counter index position
rFile>>instruction[counter];
// Increase the record counter by one
counter++;
}// End of ouster for loop
// Close the file
rFile.close();
// Return the record counter
return counter;
}// End of function
// main function definition
int main()
{
// To store the instructions read from file
string instructions[100];
int result[100];
// ofstream object for writing data
ofstream wFile;
// Creates root and temporary node
BinaryTreeNode *root = NULL,*temp;
// To store the integer data entered by the user to insert or delete
int val;
// To store user choice
string choice;
// Calls the function read instructions from file and stores the return value as number of instructions
int numberOfInstructions = readFile(instructions);
// Opens the file for reading
wFile.open("BSTResult.txt");
// Check that file can be opened or not
// is_open() function returns true if a file is open and associated with this stream object.
// Otherwise returns false.
if(!wFile.is_open())
{
// Displays error message
cout<<" Error: Unable to open the file!";
exit(0);
}// End of if condition
// Loops till number of instructions
for(int c = 0; c < numberOfInstructions; c++)
{
// Checks if the current instruction length is two
if(instructions[c].length() == 2)
{
// Extracts the instruction zero index position data and stores it in choice
choice = instructions[c].at(0);
// Using substr function extracts the integer part from the command
string value = instructions[c].substr(1);
// object from the class stringstream
stringstream convert(value);
// Converts the string number to integer number
convert >> val;
}// End of if condition
// Otherwise stores the current instruction in choice
else
choice = instructions[c];
// Checks if the command is 'i'
if(choice[0] == 'i')
{
// Calls the function to insert
root = Insert(root, val);
// Writes the heading with value
wFile<<" Insert: "<<val;
}// End of if condition
// Checks if the command is 'd'
else if(choice[0] == 'd')
{
// Calls the function to delete
root = Delete(root,val);
// Writes the heading with value
wFile<<" Delete: "<<val;
}// End of else if condition
// Checks if the choice is "opre"
else if(choice == "opre")
{
// Writes the heading to file
wFile<<" Preorder Traversal: "<<endl;
// Calls the function for in order traversal stores the count numbers
int d = Preorder(root, result);
// Loops till count numbers
for(int c = 0; c < d; c++)
// Writes the order to file
wFile<<result[c]<<endl;
}// End of else if condition
// Checks if the choice is "opost"
else if(choice == "opost")
{
// Writes the heading to file
wFile<<" Postorder Traversal: "<<endl;
// Calls the function for in order traversal stores the count numbers
int d = Postorder(root, result);
// Loops till count numbers
for(int c = 0; c < d; c++)
// Writes the order to file
wFile<<result[c]<<endl;
}// End of else if condition
// Checks if the choice is "oin"
else if(choice == "oin")
{
// Writes the heading to file
wFile<<" Inorder Traversal: "<<endl;
// Calls the function for in order traversal stores the count numbers
int d = Inorder(root, result);
// Loops till count numbers
for(int c = 0; c < d; c++)
// Writes the order to file
wFile<<result[c]<<endl;
}// End of else if condition
// Checks if the command is 'e'
else if(choice[0] == 'e')
{
wFile<<" End of Program.";
// Close the program
exit(0);
}// End of else if
// Otherwise invalid choice message is displayed and asks to re enter the choice
else
cout<<" Invalid choice! Try again.";
}// End of for loop
return 0;
}// End of main function
Sample Output:
BSTStringData.txt file contents
i3
i1
i5
i7
oin
d7
oin
opre
opost
e
BSTResult.txt file contents
Insert: 3
Insert: 1
Insert: 5
Insert: 7
Inorder Traversal:
1
3
5
7
Delete: 7
Inorder Traversal:
1
3
5
Preorder Traversal:
3
5
Postorder Traversal:
1
3