I am completely lost on how to do this project. I have done what I know and searched the internet for things to help me finish this project, but I am almost hopeless at this point. If anyone could help me out and give me a very strong push in the right direction, that would be much appreciated. Okay here it is:
Create a template based binary search tree, then use this tree as the
storage for a dictionary of words used to check the spelling of
documents. The binary tree must have the following characteristics:
It must be a binary search tree (BST), relying on the order of the
operators provided by whatever type the user of the tree chooses (in
other words, you don't have to do anything special, just use those
bool insert(T value) : inserts a value into the tree, does not allow duplicates. If the value is already in the tree do notadd the duplicate and return false, true otherwise.
void remove(T value) : deletes a value from the tree.
bool search(T value) : tests to see if a value exists in the tree.
void display() : Performs an in-order traversal of the tree, displaying the value at each node.
unsigned int numberNodes() : returns a count of all nodes in the tree.
unsigned int numberLeafNodes() : returns a count of all the leaf nodes in the tree.
unsigned int height() : returns the height of the tree.
Write a driver program that reads the file “dictionary.txt”, where
each word is on a separate line, and stores these words into your
binary search tree. After reading the dictionary into your tree, have
your program report the number of nodes, the number of leaf nodes, and
height (depth) of the tree.
The following is an example report:
-- Tree Stats --
Total Nodes: 13643 Leaf Nodes: 4545 Tree Height: 30
Next, read the file “letter.txt” and output to the console all the
misspelled words (meaning any word not found in the dictionary), keep
in mind the graders will use a different file when doing the grading.
You'll need to remove case from the words and remove any punctuation
characters from the words in the letter; the following characters
should be sufficient: “ , : . ! ? ( )
One problem you need to resolve: The dictionary is in alphabetic
order. If you insert the words in alphabetic order, your tree will
essentially be a linked list and of not much use (with respect to
performance). The words must be inserted in random order to make a
tree that can be efficiently searched. A suggestion is to use the
std::random_shuffle algorithm in the C++ standard library. This will
randomly organize the values in a vector. Then, you can iterate
through the vector and add items to your tree, resulting in a
reasonably balanced and efficient binary search tree.