needs to be written in just regular c++ , and needs to be able to fucntion with
ID: 3813742 • Letter: N
Question
needs to be written in just regular c++ , and needs to be able to fucntion with the M numbers that are 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
#include #include #include #include using namespace std; /* * Node Class Declaration */ template class BSTNode { private: T value; BSTNode *left, *right; public: BSTNode(T value) { this->value = value; left = NULL; right = NULL; } /* * Adding element to a node */ void add(T& value) { if (value value) { if (left) left->add(value); else left = new BSTNode(value); } else if (this->value add(value); else right = new BSTNode(value); } } /* * Check if node contains element */ bool contains(T& value) { if (value value) { if (left) return left->contains(value); else return false; } else if (this->value contains(value); else return false; } else { return true; } } friend class BSTHashtable; }; /* * Table Class Declaration */ class BSTHashtable { private: int size; vector* bucket; int hash(string& s) { unsigned int hashVal = 0; for (unsigned int i = 0; i 2) + s[i]; return hashVal % size; } public: BSTHashtable(int vectorSize) { size = vectorSize; bucket = new vector(size); } /* * Adding string in the table */ void add(string& s) { int index = hash(s); if (bucket->at(index) == NULL) bucket->at(index) = new BSTNode(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; coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.