needs to written in c++!!!! Objective : To be familiar binary search tree and ha
ID: 3811269 • Letter: N
Question
needs to written in c++!!!!
Objective: To be familiar binary search tree and hash table.
Description: Implement a binary search tree using hash table.
In this project, you are required to implement a binary search tree using hash table. In C++, hash table is represented by the STL class template: unordered_map. Please check this page for member functions and examples of unordered_map: http://en.cppreference.com/w/cpp/container/unordered_map.
In the binary search tree, each node contains a student object. The student object should contains M#, phone number, and address. M# is a string starting with char ‘M’ and followed by digits, such as “M12345678”. In the hash map, the key is student’s M#, and the value associated with the key is the following structure:
struct TreeNode {
Student item;
string left_child_M#;
string right_child_M#;
};
If the M# of its left or right child doesn’t exist, set its value to “M00000000”.
Requirements:
Define and implement Student class. Make sure it contains M#, phone number, and address, all getters and setters, and constructors. In addition, override < operator to compare student objects by M#, and the << operator for output.
Define and implement BST class to represent binary search tree. In this class, you should have:
A member data of the type unordered_map< string, TreeNode> to hold nodes in the binary search tree.
Member functions for in-order traversal, searching by M#, inserting a new Student object, and deleting by M#.
In the main function, which should be included in ola6.cpp file, please perform the following operation in the given step:
Create an empty binary search tree;
Insert the following M#s to the BST in the given order: M00000005, M00000003, M00000002, M00000001, M00000004, M00000006, M00000009, M00000008, M00000007. M00000010. Feel free to come up with other information for each student object. needs to be hardcoded , no input from user is needed
Perform in-order traversal to print all students in the tree;
Search the student with M# = ‘M00000007’. Print all information of the student.
Delete the student with M# = ‘M00000002’;
Perform in-order traversal to print all students in the tree;
Delete the student with M# = ‘M00000006’.
Perform in-order traversal to print all students in the tree;
Explanation / Answer
The Implementaion of binary search tree using hash table is given as following:
#include<iostream.h>
#include<string.h>
#include <cstdlib>
template <class P>
class BSTNode
{
private:
P value;
BSTNode *left, *right;
public:
BSTNode(P value)
{
this->value = value;
left = NULL;
right = NULL;
}
/*
* Add element to a node
*/
void add(P& value)
{
if (value < this->value)
{
if (left)
left->add(value);
else
left = new BSTNode(value);
}
else if (this->value < value)
{
if (right)
right->add(value);
else
right = new BSTNode(value);
}
}
bool contains(P& value)
{
if (value < this->value)
{
if (left)
return left->contains(value);
else
return false;
}
else if (this->value < value)
{
if (right)
return right->contains(value);
else
return false;
}
else
{
return true;
}
}
friend class BSTHashtable;
};
class BSTHashtable
{
private:
int size;
vector<BSTNode<string>*>* bucket;
int hash(string& s)
{
unsigned int hashVal = 0;
for (unsigned int i = 0; i < s.length(); i++)
hashVal ^= (hashVal << 5) + (hashVal >> 2) + s[i];
return hashVal % size;
}
public:
BSTHashtable(int vectorSize)
{
size = vectorSize;
bucket = new vector<BSTNode<string>*>(size);
}
void add(string& s)
{
int index = hash(s);
if (bucket->at(index) == NULL)
bucket->at(index) = new BSTNode<string>(s);
else
bucket->at(index)->add(s);
}
/*
* Check if table contains string
*/
bool contains(string& s)
{
int index = hash(s);
if (bucket->at(index) == NULL)
return false;
cout<<"String ""<<s<<"" found at index: "<<index<<endl;
return bucket->at(index)->contains(s);
}
/*
* Display Table
*/
void display()
{
for (unsigned int i = 0; i < bucket->size(); i++)
{
cout <<"[" << i << "] ";
if (bucket->at(i) != NULL)
{
BSTNode<string> *node = bucket->at(i);
display_bst(node);
}
cout << endl;
}
}
/*
Display BST
*/
void display_bst(BSTNode<string> *node)
{
if (node!=NULL)
{
display_bst(node->left);
cout << node->value << " ";
display_bst(node->right);
}
}
};
/*
* Main Contains Menu
*/
int main()
{
BSTHashtable table(10);
string str;
int choice;
while (1)
{
cout<<"Operations on BST Hash Table"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Find element in the table"<<endl;
cout<<"3.Display Table Chained with Binary Tree"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter String to be inserted: ";
cin>>str;
table.add(str);
break;
case 2:
cout<<"Enter String to search: ";
cin>>str;
if (table.contains(str) == 0)
{
cout<<"String ""<<str<<"" not found in the table"<<endl;
continue;
}
break;
case 3:
cout<<"Displaying Table Chained with Binary Tree: "<<endl;
table.display();
break;
case 4:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.