Question

In programming C language, 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.”

Again, in programming C language please.

Answer 1

Below is complete code. Please note that delete function must pass node by referance. Let me know if you have any problem or doubt. Thank you.

======================================================================

main.c

==================

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#pragma warning(disable : 4996) // for visual studio only

// define maximum length of word
#define MAX_LENGTH 100

// structure to represent node in tree
typedef struct _node* node;
struct _node {
   char* data; // data stored in node
   node left; // pointer to left child node
   node right; // pointer to right child node
};

// helper function to create a new node
node create_node() {
   // create and return an empty node
   node n = (node)malloc(sizeof(struct _node));
   n->data = NULL;
   n->left = NULL;
   n->right = NULL;
   return n;
}

// helper function to convert word into lowercase and remove punctuations
void process_word(char* word) {
   int size = 0;
   while (word[size] != '\0') {
       size++;
   }
   for (int i = 0; (i < size) && (word[i] != '\0'); i++) {
       // check for punctuation
       if (ispunct(word[i])) {
           // remove the punctuation from word
           for (int j = i; j < size; j++) {
               word[j] = word[j + 1];
           }
       }
       // convert to lowercase
       if (isupper(word[i])) {
           word[i] = 'a' + word[i] - 'A';
       }
   }
}

// FUNCTION PROTOTYPE

// inserts a node whose data is s into the tree with root node root
void insert(node root, char* s);
// deletes a node whose data is s from the tree with root node root
void delete(node root, char* s);
// prints the tree with root node root in pre - order format
void print_preorder(node root);
// prints the tree with root node root in in - order format
void print_inorder(node root);
// prints the tree with root node root in post - order format
void print_postorder(node root);
// 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
node search(node root, char* s);
// 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.
void spellcheck(node root, char* filename);

// main function to run program
int main() {
   // create a tree for words
   node dictionary = create_node();
   // open file words.txt
   FILE* file;
   file = fopen("words.txt", "r"); // open in read mode
   char word[MAX_LENGTH]; // buffer to store word read from file
   // read each word from file
   while (!feof(file)) {
       fscanf(file, "%s", word);
       // remove punctuation and convert word into lowercase
       process_word(word);
       // store the word in dictionary
       insert(dictionary, word);
   }
   // close the file
   fclose(file);

   // ask user to enter input file name to check spelling
   printf("Enter file name to check spelling: ");
   char filename[MAX_LENGTH];
   scanf("%s", filename);
   // check the spelling with dictionary
   spellcheck(dictionary, filename);

   // to delete the tree remove every node from tree
   while (dictionary != NULL) {
       delete(&dictionary, dictionary->data);
   }

   return 0;
}

// FUNCTION DEFINITION
// create recursive functions

void insert(node root, char* s) {
   // BASE CASE
   // current node is the node to be added
   if (root->data == NULL) {
       // allocate memory to hold data
       root->data = (char*)malloc(sizeof(char) * strlen(s) + 1);
       // copy s to data
       strcpy(root->data, s);
   }
   // RECURSIVE STEP
   else {
       // compare curreent node data and add child node in tree
       if (strcmp(root->data, s) > 0) {
           // add node to left of root node
           // add left child if its NULL
           if (root->left == NULL) {
               root->left = create_node();
           }
           insert(root->left, s);
       }
       else {
           // add node to right of root node
           // add right child if its NULL
           if (root->right == NULL) {
               root->right = create_node();
           }
           insert(root->right, s);
       }
   }
}

void delete(node* root, char* s) {
   // BASE CASES
   if ((*root) == NULL) {
       // word is not in the dictionary
       return;
   }
   // current node to be deleted
   if (strcmp((*root)->data, s) == 0) {
       // free memory
       free((*root)->data);
       node temp = (*root);
       // check for child nodes
       if ((*root)->left == NULL) {
           if ((*root)->right == NULL) {
               // current not is leaf node just remove the node
               *root = NULL;
           }
           else {
               // set right node at place of current node
               *root = (*root)->right;
           }
       }
       else if ((*root)->right == NULL) {
           // set right node at place of current node
           *root = (*root)->left;
       }
       else {
           // current node have both childen
           // make right node as current node and attach left node to the left of right node
           *root = (*root)->right;
           node leftmost = (*root)->left;
           // check if current root node's left is NULL
           if (leftmost == NULL) {
               (*root)->left = temp->left;
           }
           else {
               // move to left most node of current node
               while (leftmost->left != NULL) {
                   leftmost = leftmost->left;
               }
               // add deleted node's left to left most node of current node
               leftmost->left = temp->left;
           }
       }
       // free temp
       free(temp);
   }
   // RECURSIVE STEP
   else {
       // check left
       if (strcmp((*root)->data, s) > 0) {
           // note that value to delete function must pass by pointer refrence
           delete(&((*root)->left), s);
       }
       else {
           // move to right child
           delete(&((*root)->right), s);
       }
   }
}

void print_preorder(node root) {
   // BASE CASE
   if (root == NULL) {
       // print nothing for NULL
   }
   // RECURSIVE STEP
   else {
       // print current node data before child nodes
       printf("%s ", root->data);
       print_preorder(root->left);
       print_preorder(root->right);
   }
}

void print_inorder(node root) {
   // BASE CASE
   if (root == NULL) {
       // print nothing for NULL
   }
   // RECURSIVE STEP
   else {
       print_inorder(root->left);
       // print current node data in between child nodes
       printf("%s ", root->data);
       print_inorder(root->right);
   }
}

void print_postorder(node root) {
   // BASE CASE
   if (root == NULL) {
       // print nothing for NULL
   }
   // RECURSIVE STEP
   else {
       print_postorder(root->left);
       print_postorder(root->right);
       // print current node data after child nodes
       printf("%s ", root->data);
   }
}

node search(node root, char* s) {
   // BASE CASES
   if (root == NULL) {
       return NULL;
   }
   // current node data is s
   if (strcmp(root->data, s) == 0) {
       return root;
   }
   // RECURSIVE STEP
   else {
       // look for left child
       if (strcmp(root->data, s) > 0) {
           return search(root->left, s);
       }
       else {
           // return right child search
           return search(root->right, s);
       }
   }
}

void spellcheck(node root, char* filename) {
   // open file
   FILE* file = NULL;
   file = fopen(filename, "r"); // open file in read mode
   // check for valid filename
   if (file == NULL) {
       printf("Can not open file: %s\n", filename);
   }
   else {
       char word[MAX_LENGTH]; // buffer to read words from file
       char copy[MAX_LENGTH];
       int line_num = 1;
       int word_num = 1;
       // read each word from file
       while (!feof(file)) {
           fscanf(file, "%s", word);
           // create a copy of word
           strcpy(copy, word);
           // process the copy to modify it
           process_word(copy);
           // search the word in dictionary
           // if seach returns NULL then word is not in dictionary
           if (search(root, copy) == NULL) {
               // print message on cosole
               printf("Word \"%s\" on line %d, word %d mispelled or not found in dictionary.\n", word, line_num, word_num);
           }
           // check for newline
           if (getc(file) == '\n') {
               line_num++;
               word_num = 0;
           }
           word_num++;
       }
       // close the file
       fclose(file);
   }
}

==================

words.txt

==================

all work and no play makes a dull boy

==================

myInput .txt

==================

All work and no play maks Jack a dull boy.