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).

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;
}

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.

Originally Posted by tabstop

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.

I was under the impression that that was being taken care of recursively, could you give me an example of what I should change?

Originally Posted by Bizmark

I was under the impression that that was being taken care of recursively, could you give me an example of what I should change?

This is why I don't like recursive adding-to-binary-trees: to add a node you need to know the parent, and which way you traveled to get there (although, if you know the parent value, you can determine that post hoc). If you must do it recursively, you'll have to pass that parent along in the function call, or check in your left/right cases that if left/right is NULL, don't do the recursion, but add the node there.

Recursive functions are nice for simple functional utilities such as int to binary as an example. If you are dealing with a memory limited platform, then recursive methods will need to be thought out as they consume more memory than iterative solutions.

Originally Posted by iMalc

No it's not that bad. Changing 'begin' to be a pointer-to-a-pointer, or reference-to-a-pointer if this were C++, solves the problem nicely. You don't even have to return something then. Recursively building binary trees can be cleaner than the iterative solution, if you do it right.

I was actually trying that just a few minutes ago, kept on popping errors at me about how it wasn't getting the correct type. I was thinking of removing the *walk pointer as well because that would be unnecessary if using a pointer to a pointer right?

Ok I solved that problem. Now there is a problem with the following code:

Code:

 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);
                     }
                     printf("%s", fileword);
                     
                     aword = search(start, 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++;
                }
           }

I know there is something wrong with what is being tested in the loop, but I really don't know how to have the loop stop without testing fileword. Anyone have some ideas?