In this PROGRAM, you will be implementing a binary search tree. You must use a n

ID: 3833436 • Letter: I

Question

In this PROGRAM, you will be implementing a binary search tree. You must use a node-based implementation of a tree. Each node in the tree will be represented by a Node class and should have a left and right subtree pointer. Each node in your tree should hold a string (note: a string can hold more than one word) and also contain an integer count. Include the following functions for the tree. For each operation, I have included the function prototype that you must use so that your tree will interface with the main test file. This is by no means an exhaustive list of the functions that you will be writing. These functions must be public functions in your tree class.

Required Public Member Functions

-void insert(const string &): Insert an item into the binary search tree. Be sure to keep the binary search tree properties. When an item is first inserted into the tree the count should be set to 1. When adding a duplicate string (case sensitive), rather than adding another node, the count variable should just be incremented.

-bool search(const string &) const: Search for a string in the binary search tree. It should return true if the string is in the tree, and false otherwise.

-string largest( ) const: Find and return the largest value in the tree. Return an empty string if the tree is empty.

-string smallest( ) const: Find and return the smallest value in the tree. Return an empty string if the tree is empty.

-int height(const string &) const: Compute and return the height of a particular string in the tree. The height of a leaf node is 0 (count the number of edges on the longest path). Return -1 if the string does not exist.

-void remove(const string &): Remove a specified string from the tree. Be sure to maintain all binary search tree properties. If removing a node with a count greater than 1, just decrement the count, otherwise, if the count is simply 1, remove the node. You MUST follow the remove algorithm shown in the slides and discussed in class or else your program will not pass the test functions. When removing, if removing a leaf node, simply remove the leaf. Otherwise, if the node to remove has a left child, replace the node to remove with the largest string value that is smaller than the current string to remove (i.e. find the largest value in the left subtree of the node to remove). If the node has no left child, replace the node to remove with the smallest value larger than the current string to remove (i.e. find the smallest value in the right subtree of the node to remove).

Printing the tree

Print the tree in the following manners. When printing a node, print the string followed by the count in parentheses followed by a , and one space. You must follow these guidelines exactly. For example: goodbye(1), Hello World(3),

-void preOrder( ): Traverse and print the tree in preorder notation following the printing guidelines specified above.

-void inOrder( ):Traverse and print the tree in inorder notation following the printing guidelines specified above.

-void postOrder( ): Traverse and print the tree in postorder notation following the printing guidelines specified above.

Note about recursion

Some of the above functions used to interface with the main test file are not conducive for recursive methodology. However, you must write the inOrder, preOrder, postOrder, search, and remove functions recursively (you will lose points if you do not do these recursively). This may require you to overload 1 or more of the functions. For instance, preOrder is called from main but is not passed any parameter (you should not be able to pass the root from main because it should be a private variable of your tree class). However, you can overload the preOrder function so that it will operate recursively. For example, your preOrder function should look like this:

and you will write the preOrder code within the recursive function that takes a node as a parameter. You may need to do something similar for the inOrder, postOrder, search, and/or remove functions so that you can write these functions recursively. Should these recursive helper functions be public or private?

Provided Files

***BSTree.h***

#ifndef __BSTREE_H__
#define __BSTREE_H__

#include "Node.h"

using namespace std;

class BSTree {

private:
Node *root;

private:
void preOrder(Node *) const;

public:
void insert(const string &);
bool search(const string &) const;
void inOrder( ) const;
void postOrder( ) const;
void preOrder( ) const;
string largest( ) const;
string smallest( ) const;
int height(const string &) const;
void remove(const string &);
};

#endif

****main.cpp****

#include
#include "BSTree.h"

using namespace std;

void printOrders(BSTree *tree) {
cout << "Preorder = ";
tree->preOrder( );
cout << "Inorder = ";
tree->inOrder( );
cout << "Postorder = ";
tree->postOrder( );
}

int menu() {
int choice = 0;
cout << endl << "Enter menu choice: ";
cout << endl;
cout
<< "1. Insert" << endl
<< "2. Remove" << endl
<< "3. Print" << endl
<< "4. Search" << endl
<< "5. Smallest" << endl
<< "6. Largest" << endl
<< "7. Height" << endl
<< "8. Quit" << endl;
cin >> choice;

// fix buffer just in case non-numeric choice entered
// also gets rid of newline character
cin.clear();
cin.ignore(256, ' ');
return choice;
}

int main( ) {

BSTree tree;

int choice = menu();

string entry;

while (choice != 8) {

if (choice == 1) {
cout << "Enter string to insert: ";
getline(cin, entry);
cout << endl;

tree.insert(entry);

} else if (choice == 2) {
cout << "Enter string to remove: ";
getline(cin, entry);
cout << endl;

tree.remove(entry);

} else if (choice == 3) {
printOrders(&tree);

} else if (choice == 4) {
cout << "Enter string to search for: ";
getline(cin, entry);
cout << endl;

if (tree.search(entry)) {
cout << "Found" << endl;
} else {
cout << "Not Found" << endl;
}

} else if (choice == 5) {
cout << "Smallest: " << tree.smallest() << endl;

} else if (choice == 6) {
cout << "Largest: " << tree.largest() << endl;

} else if (choice == 7) {
cout << "Enter string: ";
getline(cin, entry);
cout << endl;
cout << "Height of subtree rooted at " << entry << ": "
<< tree.height(entry) << endl;

}
//fix buffer just in case non-numeric choice entered
choice = menu();
}

return 0;
}

You will need to add other private helper functions to this BSTree class (constructor, deconstructor, and another else included) and you will need to make your own Node class.

Suggested Algorithms:

(1) Recursive implementation of inorder traversal

void inorder(Node* nodePtr)

if ( nodePtr ) {

inorder (nodePtr->left)

print node

inorder (nodePtr->right)

}

(2) -Make a stack of node pointers

-Operands - push a new tree onto the stack

-Operators - pop two trees from the stack. Use the operator as the root of a new tree with the popped trees as children. Push a new tree onto the stack

(3)Recursive implementation of search (private)

Node * search (Node *nodePtr, itemtype key)

if (!nodePtr){

return 0

}else if (nodePtr->item == key){

return nodePtr

}else if (nodePtr->item > key){

return search(nodePtr->left, key)

}else{

return search(nodePtr->right, key)

}

(4)Remove

Five possible situations

-Item not found

-Removing a leaf

-Removing a node with one child - right only

-Removing a node with one child - left only

-Removing a node with two children

Deletion - Removing a node with children

-Otherwise the node has children - find replacement node

-If the left child exists

-----Replace node information with the largest value smaller than the value to remove

-----findMax(leftChild)

-Else there is a right child

------Replace node information with the smallest value larger than value to remove

------findMin(rightChild)

- Splice out replacement node (call remove recursively)

-Just copy in info of replacement node over the value to remove (overload = if necessary) Note - this is NOT the best solution if you have a large data structure. The overhead of the copy is too great and you should move the node instead.

-Delete replacement node if leaf

Explanation / Answer

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include <string.h>
using namespace std;
//Structure definition
struct BinaryTreeNode
{
//Structure member
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};//End of structure

//Returns the node having minimum value
BinaryTreeNode* FindMin(BinaryTreeNode *tnode)
{
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)
return FindMin(tnode -> left);
else
return tnode;
}//End of function

//Returns the node having maximum value
BinaryTreeNode* FindMax(BinaryTreeNode *tnode)
{
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 -> right)
return(FindMax(tnode -> right));
else
return tnode;
}//End of function

//Insert a node
BinaryTreeNode *Insert(BinaryTreeNode *tnode,int value)
{
if(tnode == NULL)
{
BinaryTreeNode *temp;
temp = new BinaryTreeNode;
temp -> data = value;
temp -> left = temp -> right = NULL;
return temp;
}
if(value >(tnode -> data))
{
tnode -> right = Insert(tnode -> right, value);
}
else if(value < (tnode -> data))
{
tnode -> left = Insert(tnode -> left, value);
}
//Else there is nothing to do as the data is already in the tree.
return tnode;
}//End of function

BinaryTreeNode * Delete(BinaryTreeNode *tnode, int value)
{
BinaryTreeNode *temp;
if(tnode == NULL)
{
cout<<"Element Not Found";
}
else if(value < tnode -> data)
{
tnode -> left = Delete(tnode -> left, value);
}
else if(value > tnode -> data)
{
tnode -> right = Delete(tnode -> right, value);
}
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 -> data = temp -> data;

//As we replaced it with some other node, we have to delete that node
tnode -> right = Delete(tnode -> right, temp -> data);
}
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)
tnode = tnode -> right;
else if(tnode -> right == NULL)
tnode = tnode -> left;
//Delete temp
free(temp);
}//End of inner else
}//End of outer else
return tnode;
}//End of function

//Search for a node
BinaryTreeNode * Find(BinaryTreeNode *tnode, int value)
{
if(tnode == NULL)
{
//Element is not found
return NULL;
}
if(value > tnode -> data)
{
//Search in the right sub tree.
return Find(tnode -> right, value);
}
else if(value < tnode -> data)
{
//Search in the left sub tree.
return Find(tnode -> left, value);
}
else
{
//Element Found
return tnode;
}
}//End of function

//Inorder traversal
void Inorder(BinaryTreeNode *tnode)
{
if(tnode == NULL)
{
return;
}
Inorder(tnode -> left);
cout<<tnode -> data<<" ";
Inorder(tnode -> right);
}//End of function

int depth(BinaryTreeNode *tnode)
{
if (tnode == NULL)
return 0;
return max( depth(tnode->left), depth(tnode->right) ) + 1;
}
//Main function
int main()
{
//Creates root and temporary node
BinaryTreeNode *root = NULL,*temp;
int val, x, y;
int ch;
//Loops till user choice is 'e'
while(1)
{
//Displays the menu
cout<<" 1 Insert 2 Delete 3 Print 4 Search 5 Smallest 6 Largest 7 Height 8 Quit ";
cout<<"Enter your choice: ";
cin>>ch;
//Checks the choice
switch(ch)
{
case 1:
cout<<" Enter the value to insert: ";
cin>>val;
root = Insert(root, val);
break;
case 2:
cout<<" Enter the value to delete: ";
cin>>val;
root = Delete(root,val);
break;
case 3:
cout<<" Traversal : ";
Inorder(root);
break;
case 4:
cout<<" Enter the number to Search: ";
cin>>val;
temp = Find(root, val);
if(temp == NULL)
cout<<" Not Found";
else
cout<<" Found "<<temp->data;
break;
case 5:
temp = FindMin(root);
cout<<" Smallest: "<<temp->data;
break;
case 6:
temp = FindMax(root);
cout<<" Largest: "<<temp->data;
break;
case 7:
cout<<" Height of tree: "<<depth(root);
break;
case 8:
exit(0);
default:
cout<<" Invalid choice:";
}
}//End of while
return 0;
}//End of main

Output: