BST Spell Check

Your assignment is to write a program that creates a binary tree of words to be used as a spell checking device for various text files. The list of words will come from a file "words.txt".

Your program is to read through the "words.txt" file and insert the word on that line into the tree in lexicographic order (also known as Dictionary order). Words in the file will be separated by spaces. Once this is done, your program should then prompt the user to enter a text file and then scan through each word in the file to check spelling.

Your program must be able to insert words into and delete words from the tree. It must also be able to search the tree for a given string (this is how the spell check is done), and print the tree in pre order, in order, and post order.

The functions that do this should look as follows:

• void insert(root, s): node x char* -> none
  • inserts a node whose data is s into the tree with root node root
• void delete(root, s): node x char* -> none
  • deletes a node whose data is s from the tree with root node root
• void print_preorder(root): node -> none
  • prints the tree with root node root in pre-order format
• void print_inorder(root): node -> none
  • prints the tree with root node root in in-order format
• void print_postorder(root): node -> none
  • prints the tree with root node root in post-order format
• node search(root, s): node x char* -> node
  • searches a tree with root node root for a node whose data is s, if it is found then that node is returned, otherwise a NULL node is returned

For the spell-checking portion of the program, there should be a function spellcheck which takes as arguments a root node for your tree, and a string for a filename. Spellcheck should scan the file at that location word by word and check if that word is in the tree, ignoring capitalization and punctuation (apostrophes are not considered to be punctuation). If the word is not found then a message should be printed to the console indicating that word is not found / misspelled. The message should indicate the word's position in the file.

• void spellcheck(root, filename): node x char* -> none
  • Scans a text file (filename) word by word, prints a message to the console if a word is not found in the tree of correct words.

Sample Input/Output

words.txt: "all work and no play makes a dull boy"
myInput.txt: "All work and no play maks Jack a dull boy."

Output:

"Word "maks" on line 1, word 6 mispelled or not found in dictionary."
"Word "Jack" on line 1, word 7 mispelled or not found in dictionary."