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

Code written in C language...

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

#define Max_Len 100 // defines maximum length of the word

typedef struct _node* node;
struct _node    // node structure
{
   char* val;
   node right; // pointer to right child
   node left; // pointer to left child
};

node new_node() // creating new node
{
   node n = (node)malloc(sizeof(struct _node));
   n->val = NULL;
   n->right = NULL;
   n->left = NULL;
   return n;
}
// Function below processes the word ( punctuation removal and conversion to lowercase )
void process_word(char* word)
{
   int len = 0;
   while (word[len] != '\0')
       len++;
   for (int i = 0; (i < len) && (word[i] != '\0'); i++)
{
       if (ispunct(word[i])) // checking and removing punctuations
      {
           for (int j = i; j < len; j++)
               word[j] = word[j + 1];
       }
       if (isupper(word[i])) // conversion to lowercase
           word[i] = 'a' + word[i] - 'A';
   }
}

// Function declarations...
void insert(node root, char* s); // fun to insert a node having s value into the tree with root node root

void delete(node root, char* s); // fun to delete the node with s value from the tree with root node root

void disp_preorder(node root); // prints the tree in pre_order format

void disp_inorder(node root); // prints the tree in in_order format

void disp_postorder(node root); // prints the tree in post_order format

node search(node root, char* s); // searches for the node having value s

void spellcheck(node root, char* filename); // checks every word of the file wether it is present in the tree of correct words or not

int main()
{
   node dictionary = create_node();
  
   FILE* file;
   file = fopen("words.txt", "r"); // open file in read mode
   char word[Max_Len]; // buffer to store word read from file
  
   while (!feof(file)) // reading each word from file
   {
       fscanf(file, "%s", word);
       process_word(word);
       insert(dictionary, word);
   }
   fclose(file); // closing the file after reading

   printf("Enter file name : ");
   char file_name[Max_Len];
   scanf("%s", file_name);
   spellcheck(dictionary, file_name);

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

// Function definitions

void insert(node root, char* s)
{
   if (root->val == NULL)
   {
       // Dynamic memory allocation
       root->val = (char*)malloc(sizeof(char) * strlen(s) + 1);
       strcpy(root->val, s);
   }
   else
   {
    
       if (strcmp(root->val, s) > 0)   // compare curreent node data
       {
           if (root->left == NULL) // add left child if its NULL
               root->left = create_node();
           insert(root->left, s);
       }
       else
      {
           if (root->right == NULL) // add right child if its NULL
               root->right = create_node();
           insert(root->right, s);
       }
   }
}

// *NOTE delete function must pass node by referance
void delete(node* root, char* s)
{
   if ((*root) == NULL)
       return;
  
   if (strcmp((*root)->val, s) == 0)
{
       free((*root)->val);
       node temp = (*root);
       if ((*root)->left == NULL)
       {
           if ((*root)->right == NULL)   
               *root = NULL; //It's a leaf node just remove the node
           else
               *root = (*root)->right; //make right node as current node
       }
       else if ((*root)->right == NULL)
      {
           *root = (*root)->left; // set right node at the current node
       }
       else
      {
           /* current node have both childen , then make right node as current node and attach left node to the left of right node */
           *root = (*root)->right;
           node leftmost = (*root)->left;
           if (leftmost == NULL)
               (*root)->left = temp->left;
           else
           {
               while (leftmost->left != NULL) // left most node of current node
                   leftmost = leftmost->left;
               leftmost->left = temp->left; // add deleted node's left to left most node of current node
           }
       }
       free(temp);
   }
   else
{
       if (strcmp((*root)->val, s) > 0)
           // **note that value to delete function must pass by pointer refrence
           delete(&((*root)->left), s);
       else
           delete(&((*root)->right), s); // go to right child
   }
}
void disp_preorder(node root)
{
   if (root == NULL)
{
       // Null tree
   }
   else
   {
       // print current node data before child nodes ( pre_order )
       printf("%s ", root->val);
       disp_preorder(root->left);
       disp_preorder(root->right);
   }
}

void disp_inorder(node root)
{
   if (root == NULL)
{
       // Pring nothing (NULL)
   }
   else
{
        // print current node data in between child nodes
       disp_inorder(root->left);
       printf("%s ", root->val);
       disp_inorder(root->right);
   }
}

void disp_postorder(node root)
{
   if (root == NULL)
{
       // print nothing (NULL)
   }
   else
   {
         // print current node data after child nodes
       disp_postorder(root->left);
       disp_postorder(root->right);
       printf("%s ", root->val);
   }
}

node search(node root, char* s)
{
   if (root == NULL)
       return NULL;

   if (strcmp(root->val, s) == 0)
       return root;
  
   else
   {
       if (strcmp(root->val, s) > 0)
           return search(root->left, s);
       else
           return search(root->right, s);
   }
}

void spellcheck(node root, char* filename)
{
   FILE* file = NULL;
   file = fopen(filename, "r"); // open file in read mode

   if (file == NULL)
       printf("Can not open file: %s\n", filename);
  
   else
   {
       char word[Max_Len]; // buffer to read words from file
       char copy[Max_Len];
       int l_num = 1; // line number
       int w_num = 1; // word number
       while (!feof(file)) // reading each word of file
       {
           fscanf(file, "%s", word);
           strcpy(copy, word);
           process_word(copy);
           /* search the word in dictionary if seach results NULL then word is not present in the dictionary */
           if (search(root, copy) == NULL)
          {
               printf("Word \"%s\" on line %d, word %d mispelled or not found in dictionary.\n", word, l_num, w_num);
           }
           if (getc(file) == '\n') // checking for new line
          {
               l_num++;
               w_num = 0;
           }
           w_num++;
       }
       fclose(file);
   }
}

/*
words.txt
    all work and no play makes a dull boy

inputfile.txt
    All work and no play maks Jack a dull boy.
*/

Output:

Enter file name : inputfile.txt

Word "marks" on line 1, word 6 mispelled or not found in dictionary.

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