needs to be written in c++ , and needs to store the M number provided in the ins
ID: 3812904 • Letter: N
Question
needs to be written in c++ , and needs to store the M number provided in the instructions
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.
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# = ‘M00000005’.
Perform in-order traversal to print all students in the tree;
Explanation / Answer
Ans: Program::
// iostream
#include <iostream>
// includes_string
#include <string>
// vector incld
#include <vector>
// cstdlib includes
#include <cstdlib>
// name_space
using namespace std;
// node class T
template <class T>
// BSTNode class
class BSTNode
{
// private
private:
// T value
T value;
// left. right
BSTNode *left, *right;
// public
public:
// BSTNODE()
BSTNode(T value)
{
// this
this->value = value;
// left equals null
left = NULL;
// right equals null
right = NULL;
}
// Add element to the node
void add(T& value)
{
// if
if (value < this->value)
{
if (left)
// add value
left->add(value);
// else
else
// BSTNode_value
left = new BSTNode(value);
}
// this value
else if (this->value < value)
{
// if
if (right)
// add value
right->add(value);
// else
else
// BSTNode
right = new BSTNode(value);
}
}
// Chck if the node contains an element
bool contains(T& value)
{
// value
if (value < this->value)
{
// left
if (left)
// left
return left->contains(value);
//else
else
// return false
return false;
}
// else if
else if (this->value < value)
{
// right
if (right)
// contains
return right->contains(value);
// else
else
// return false
return false;
}
// else
else
{
// true
return true;
}
}
// BSTHashtable
friend class BSTHashtable;
};
// table_class
class BSTHashtable
{
// private
private:
// size
int size;
// vector . bucket
vector<BSTNode<string>*>* bucket;
// int hash
int hash(string& s)
{
// unsigned int equals 0
unsigned int hashVal = 0;
// for loop
for (unsigned int i = 0; i < s.length(); i++)
// hashval ^ cond
hashVal ^= (hashVal << 5) + (hashVal >> 2) + s[i];
// return
return hashVal % size;
}
// puyblic
public:
BSTHashtable(int vectorSize)
{
// size
size = vectorSize;
// bucket
bucket = new vector<BSTNode<string>*>(size);
}
// add string
// add
void add(string& s)
{
// index
int index = hash(s);
// null
if (bucket->at(index) == NULL)
// index
bucket->at(index) = new BSTNode<string>(s);
// else
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
void display()
{
// unsigned int
for (unsigned int i = 0; i < bucket->size(); i++)
{
// cout
cout <<"[" << i << "] ";
// bucket
if (bucket->at(i) != NULL)
{
// string *node
BSTNode<string> *node = bucket->at(i);
// display
display_bst(node);
}
cout << endl;
}
}
//display
void display_bst(BSTNode<string> *node)
{
// if
if (node!=NULL)
{
// left
display_bst(node->left);
//value
cout << node->value << " ";
display_bst(node->right);
}
}
};
// main
int main()
{
// BSTHash_table
BSTHashtable table(10);
// str
string str;
// choice
int choice;
// while
while (1)
{
// cout
cout<<" ----------------------"<<endl;
// operations on bst
cout<<"Operations on the BST Hash Table"<<endl;
cout<<" ----------------------"<<endl;
// insert
cout<<"1.Insert an element into_table"<<endl;
// find
cout<<"2.Find an element in table"<<endl;
cout<<"3.Display the Table Chained with the Binary Tree"<<endl;
cout<<"4.Exit"<<endl;
// enter choice
cout<<"Enter_choice: ";
cin>>choice;
switch(choice)
{
// case-1
case 1:
// cout
cout<<"Enter the string to inserted: ";
// cin
cin>>str;
// add
table.add(str);
break;
// case-2
case 2:
cout<<"Enter String to search: ";
cin>>str;
if (table.contains(str) == 0)
{
// cout
cout<<"String ""<<str<<"" doesnt found in table"<<endl;
// continue
continue;
}
// break
break;
// case-3
case 3:
// cout display
cout<<"Displayng the Table_Chained wit a Binary_Tree: "<<endl;
// display
table.display();
break;
// case-4
case 4:
// exit
exit(1);
// default
default:
// enter option
cout<<" Enter the correct_option ";
}
}
// return
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.