Thread: Help! Losing the top of my binary search tree...

Hi, I'm doing a project for my Computer Science 1 class and I'm pretty much finished. However, I have a problem (I think this is the problem) with losing the top of my binary search tree. The point of this program is to take in a file with words in it (these are correct spellings) and put the words into a binary search tree (BST), then spell check another file using the words in the BST.

Here's the code (I posted what is happening after the code):

Code:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

struct treenode
{
       char word[50];
       
       struct treenode *left;
       struct treenode *right;

};

struct treenode *insert(struct treenode *begin, char x[50]);
char *search(struct treenode *top, char w[50]);



main()
{
      char diction[50], filename[50], theword[50], fileline[200], filenull[50];
      char *p, *aword, *fileword;
      int tst = 0, linecnt = 1, miss = 0, wordcnt = 1, run = 0;
      struct treenode *root = NULL;
      
      fileword = (char *)calloc(50, sizeof(char));
      char del[] = "~!@#$%^&*()-_=+[]{}\\|;:\'\",.<>/\? \n\t\r";
      
      FILE *di; 
      FILE *file;
      
      printf("Welcome to the Spell Checker!");
      printf("\nPlease enter in the dictionary filename: ");
      
      fgets(diction, sizeof(diction), stdin);
      //Removes the \n that ENTER adds into the filename input
      if((p = strchr(diction, '\n')) != NULL)
      {
            *p = '\0';
      }
      
      
       //Opens the file
       di = fopen(diction, "r");
       
       if(di == NULL)
       {
             printf("\nThe dictionary file is empty!\n");
             tst = 1;
       }
       
       //Creates the binary tree
       if(tst != 1)
       {
            while(!feof(di))
            {
                 fscanf(di, "%s", theword);
                 printf("%s\n", theword);
                 root = insert(root, theword);
             }
       }
      
      
      if(tst != 1) 
      {       
           printf("\nPlease enter in the name of the file you would like to spell check: ");
      
           fgets(filename, sizeof(filename), stdin);
           //Removes the \n that ENTER adds into the filename input
           if((p = strchr(filename, '\n')) != NULL)
           {
                *p = '\0';
           }
      
           //Opens the file
           file = fopen(filename, "r");
       
           if(file == NULL)
           {
                printf("\nThe file you wanted to check is empty!\n");
                tst = 1;
           }
           
           if(tst != 1)
           {
                while(!feof(file))
                {
                     fgets(fileline, 500, file);
                     
                     printf("%s\n", fileline);
                     
                     do{
                     if(run == 0)
                     {
                          fileword = strtok(fileline, del);
                          run = 1;
                     }
                     else
                     {
                         fileword = strtok(NULL, del);
                     }
                     
                     aword = search(root, fileword);
                
                     if(strcmp(aword, "toupper") == 0)
                     {
                         printf("%s: on line %d needs to be capitalized.\n", fileword, linecnt);
                         miss = 1;
                     }
                     else if(strcmp(aword, "null") == 0)
                     {
                          printf("%s: on line %d is misspelled.\n", fileword, linecnt);
                     }    miss = 1;
                     }while(fileword != NULL);
                     linecnt++;
                }
           }
           if(miss == 0)
           {
                   printf("The file had nothing misspelled!\n");
           }
           
       }//End if    
       system("pause");
                          
                
      
      

}//End Main

struct treenode *insert(struct treenode *begin, char x[50])
{
     struct treenode *top = begin;
     struct treenode *walk = begin;
     
     if(walk == NULL)
     {
            walk = (struct treenode*)malloc(sizeof(struct treenode));
		    strcpy(walk->word, x);
		    walk->left = NULL;
		    walk->right = NULL;
      }
      else if(strcmp(x, walk->word) < 0)
      {
           insert(walk->left, x);
      }
      else if(strcmp(x, walk->word) > 0)
      {
           insert(walk->right, x);
      }
      return top;
}//End Insert

/*Returns "null" if tree is empty or word not found, returns "toupper" if the word was found but first char needs to be capitalized,
          returns "good" if word was found and meets the lowercase and uppercase rules*/

char *search(struct treenode *top, char w[50])
{
     struct treenode *walk = top;
     char *ret = (char *)calloc(50, sizeof(char));
     
     printf("%s\n", &walk->word);
     
     if(walk == NULL)
     {
          return ret = "null";
     }
     else if(strcmp(w, walk->word) < 0)
     {
          return search(walk->left, w);
     }
     else if(strcmp(w, walk->word) > 0)
     {
          return search(walk->right, w);
     }
     else if(strcmp(w, walk->word) == 0)
     {
          
          //Checks to see if the first character in the string is uppercase
          if(walk->word[0] == toupper(walk->word[0]))
          {
               if(w[0] == walk->word[0])
               {
                    return ret = "good";
               }
               else
               {
                   return ret = "toupper";
               }
          }
          return ret = "good";
     }
              
}//End search

So whats going on is that in my search function I put printf("%s\n", &walk->word). This is so that I can see the words as their being searched through my BST. Only problem is it keeps printing (NULL). So either the words aren't being saved in my BST or the root of my BST is lost while the words are being saved to it in my insert function. Anyone see a way to fix this or any other problems that could be causing it?

In the walk==NULL case, you need to set top to point to the new-and-improved walk, as well (otherwise you'll return the same top you started with, which is, as mentioned, NULL).

Probably the fact that you never set a link from the parent to the added node.

Originally Posted by tabstop

Probably the fact that you never set a link from the parent to the added node.

Where do you see this? Heres what I have when I'm first making the BST:

Code:

 if(tst != 1)
       {
            while(!feof(di))
            {
                 fscanf(di, "%s", theword);
                 printf("%s\n", theword);
                 root = insert(root, theword); //This is where the *top in the insert function is assigned back to the root
             }
       }

Isn't root=insert(root, theword); returning the top of the BST to the parent?

Originally Posted by Bizmark

Where do you see this? Heres what I have when I'm first making the BST:

Code:

 if(tst != 1)
       {
            while(!feof(di))
            {
                 fscanf(di, "%s", theword);
                 printf("%s\n", theword);
                 root = insert(root, theword); //This is where the *top in the insert function is assigned back to the root
             }
       }

Isn't root=insert(root, theword); returning the top of the BST to the parent?

Um ... no? It returns the top of the list to the top of the list.

When you malloc your new node, you need to set parent->left or parent->right (as appropriate) to point to the new node, otherwise it just goes away where you can't find it anymore.

You have to return 0 at the end of your main().

Going along with that, avoid implicit declarations of main().

Here:

Code:

int main(void)
{
     //...
     return 0;
}