Binary Search C++ Example input and output i3 i1 i5 i7 oin 1 3 5 7 d7 oin 1 3 5

Question

Binary Search C++

Example input and output

i3

i1

i5

i7

oin

1

3

5

7

d7

oin

1

3

5

opre

3

1

5

opost

1

5

3

e

Binary Search Trees Description In this lab your goal is to implement standard operations of binary search trees, including 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 examples 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 following · i(key): 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. opre: output all keys via preorder walk. opost: output all keys via postorder walk oin: output all keys via inorder walk. . e: finish your program

Explanation / Answer

// File Name: BSTMenuString.cpp

#include<iostream>
#include <sstream> // For stringstream to convert string to integer
#include <cstdlib> // For exit() function
#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
*/
void Inorder(BinaryTreeNode *tnode)
{
// Checks if tree is empty
if(tnode == NULL)
return;
// Recursively calls the left child node
Inorder(tnode -> left);
// Displays data
cout<<tnode -> value<<endl;
// Recursively calls the right child node
Inorder(tnode -> right);
}//End of function

/* Function for Pre order traversal
* Parameters:
* *tnode: pointer to root node
*/
void Preorder(BinaryTreeNode *tnode)
{
// Checks if tree is empty
if(tnode == NULL)
return;
// Displays data
cout<<tnode -> value<<endl;
// Recursively calls the left child node
Preorder(tnode -> left);
// Recursively calls the right child node
Preorder(tnode -> right);
}// End of function

/* Function for Post order traversal
* Parameters:
* *tnode: pointer to root node
*/
void Postorder(BinaryTreeNode *tnode)
{
// Checks if tree is empty
if(tnode == NULL)
return;
// Recursively calls the left child node
Postorder(tnode -> left);
// Recursively calls the right child node
Postorder(tnode -> right);
// Displays data
cout<<tnode -> value<<endl;
}// End of function

// main function definition
int main()
{
// 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;
// Loops till user choice is is not 'e'
while(1)
{
// Displays the menu
cout<<" i(key) Insert(key) d(key) Delete(key) opre Preorder Traversal opost Post order Traversal oin Inorder Traversal e Exit ";
// Accepts user choice
cout<<"Enter your choice: ";
cin>>choice;
// Using substr function extracts the integer part from the command
string value = choice.substr(1);
// object from the class stringstream
stringstream convert(value);

// Converts the string number to integer number
convert >> val;

// Checks if the command is 'i'
if(choice[0] == 'i')
// Calls the function to insert
root = Insert(root, val);

// Checks if the command is 'd'
else if(choice[0] == 'd')
// Calls the function to delete
root = Delete(root,val);

// Checks if the choice is "opre"
else if(choice == "opre")
// Calls the function for pre order traversal
Preorder(root);

// Checks if the choice is "opost"
else if(choice == "opost")
// Calls the function for post order traversal
Postorder(root);

// Checks if the choice is "oin"
else if(choice == "oin")
// Calls the function for in order traversal
Inorder(root);

// Checks if the command is 'e'
else if(choice[0] == 'e')
{
cout<<" 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 while
return 0;
}// End of main function

Sample Output:

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: i22

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: i78

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: i9

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: opre
22
9
78

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: opost
9
78
22

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: oin
9
22
78

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: d88

Element Not Found
i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: d9

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: oin
22
78

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: i899

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: i8779

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: oin
22
78
899
8779

i(key) Insert(key)
d(key) Delete(key)
opre Preorder Traversal
opost Post order Traversal
oin Inorder Traversal
e Exit
Enter your choice: e

End of Program.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.