Thread: please help with binary tree, urgent.

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    2

    Question please help with binary tree, urgent.

    Using Dev c++ for windows. I am having trouble with my binary tree program. Designed to read in a file which contains names of 3 files and read each one of the 3 files and perform operations. My biggest problem is with the first file. The first line is an integer which tells how many chapters are in the book. From there it will read the next line which contains the title of the chapter then the number of words in that chapter. Will read each word individually and check to see if its already in the tree if it is, then increment the frequency of the word and not add a duplicate node to the tree, but if its not found then add the word to the tree. From the main program I am calling a function to create a new chapter, within that function I am calling a function to search my binary tree for that chapter and tell me if that word exists by returning 1 or 0. The first word always gets added to the tree because the tree is null, no values have been added to it. Problem is every word after the first word, isn't being inserted into the tree. The left and right node of each node is always null. I checked my insert function many times, and spent hours debugging, but cant come up with a solution. Can someone give me some direction? Here is my code from my program.

    Code:
    struct binaryTree{
           int frequency;       
           struct binaryTree * left;
           struct binaryTree * right;
           char word[20];
           };
    struct chapter{
           struct chapter *next;
           struct binaryTree *words;
           int distinct;
           int height;
           char chapterTitle[20];
    };
    
    struct chapter * readChapters(struct chapter * list, FILE * infile);
    struct binaryTree * addWord(struct binaryTree * words, char * word);
    int searchFrequency(struct binaryTree * words, char * word);
    struct binaryTree * insertWord(struct binaryTree * words, struct binaryTree * temp);
    void deleteWord(struct binaryTree * words);
    
    
    main(){
           FILE * infile;
           char fileName[20], file1[10], file2[10], file3[10], word[20];
           int totalChapters = 0, counter=0, totalSearching=0, totalDeleting=0;
           struct chapter * list = NULL;
          // list = intializeChapter(list);
           
           //Get filename which holds the names of the other 3 files.
           printf("Enter the name of the file: ");
           scanf("%s", &fileName);
           
           infile = fopen(fileName, "r");
           //scan in the three file names
           fscanf(infile, "%s%s%s", &file1,&file2,&file3);
           //close file which contains names of three other files.     
           fclose(infile);
           //open file number one of the three
           infile = fopen(file1, "r");
           //scan in the total number of chapters
           fscanf(infile,"%d", &totalChapters);
           //scan each chapter and contents
           for(counter=0; counter < totalChapters; counter++){
                   //read chapter words                                                           
                   list =  readChapters(list, infile);                               
                                                
           }
          
            //close file 1
            fclose(infile);
           
            //open file 2 for searching
            infile = fopen(file2, "r");
            printf("\nSEARCHING\n");
           
            fscanf(infile, "%d", &totalSearching);
            //read and search each word in the book
            for(counter=0; counter<totalSearching; counter++){
                          
                      fscanf(infile, "%s", word);
                      printf("%s:\n", word);
                      //search function  also at bottom.                    
                          
            }
             //close file 2               
            fclose(infile);
            //open file 3 for deleting
            infile = fopen(file3, "r");
            printf("\nDELETION\n");
           
            fscanf(infile, "%d", &totalDeleting);
           
            for(counter=0; counter<totalDeleting; counter++){
                          
                      fscanf(infile, "%s", word);
                      printf("%s:\n", word);
                      //delete function at bottom. didnt have time to write it into main.                      
            }
                
           
            //close file 3
            fclose(infile);
            system("pause");      
           
           
    }
    //create a new chapter and scan in content
    struct chapter * readChapters(struct chapter * list, FILE * infile){
         int totalWords=0, counter=0;
         char word[20];
         //create new chapter
         struct chapter * newChapter = NULL, * current = NULL ;
         newChapter = (struct chapter *) malloc (sizeof(struct chapter));
         newChapter->words = NULL;
         newChapter->next = NULL;
         newChapter->distinct = 0;
         newChapter->height = 0;
         //scan in chapter title and total words in this chapter  
           
         fscanf(infile, "%s%d", newChapter->chapterTitle, &totalWords);
        
         printf("-----------------\n%s\n%d\n", newChapter->chapterTitle, totalWords);
         
         //scan each word in the this chapter
         for(counter=0; counter < totalWords; counter++){
                        
             fscanf(infile, "%s", &word);
             //printf("%s\n", word);
             newChapter->words = addWord(newChapter->words, word);
                       
                        
         }
        
        
         if(list ==NULL){
                
             return newChapter;
                
         }else{
              current = list;
              while(current->next != NULL){
                    current = current->next;
                     
              }
                            
              current->next = newChapter;
              
              
              
              return list;
              
          }
        
         
       
         
         
    }
    //add word to chapter
    struct binaryTree * addWord(struct binaryTree * words, char * word){
         int results = 1; 
         struct binaryTree * newWord = (struct binaryTree*) malloc (sizeof(struct binaryTree));
         struct binaryTree * newPlace = NULL;
         strcpy(newWord->word,word);
         newWord->left = NULL;
         newWord->right = NULL;
         newWord->frequency = 1;
         //see if word exists
         results = searchFrequency(words, word);
         
         //if it doesnt exist then add it to the chapter
         if(results == 0){
        
             if(words == NULL){
                     printf("%s\n", newWord->word);
                     return newWord;
             }
             else{
                  //add the word to the binary tree
                 newPlace = insertWord(words, newWord);
                 
                 newPlace = newWord;
                 printf("%s\n", newPlace->word);
                 return words;
             }
             
           
         }
       
    
                
                 
    }
    //see if word exists, if it does increment the frequency
    int searchFrequency(struct binaryTree * words, char * word){
       
        if(words == NULL){
                     return 0;
        }
        else if(strcmp(words->word, word) < 0){
                 searchFrequency(words->right, word);
        }else if(strcmp(words->word, word) > 0){
                    searchFrequency(words->left, word);                  
        }
         else //(strcmp(words->word, word) == 0)
        {            
                     words->frequency +=1;
                     return 1;
        }
    
    }
    //insert the word into the 
    struct binaryTree * insertWord(struct binaryTree * words, struct binaryTree * newWord){
       
        if(words == NULL){
                 return words;
                  
         }
         else {
              if(strcmp(words->word, newWord->word) < 0){
                words->right = insertWord(words->right, newWord);
                }
              else if(strcmp(words->word, newWord->word) > 0){
                words->left = insertWord(words->left, newWord);       
                          
                }
          }
         return words;
        
        /* if(words == NULL){
                 return words;
                  
         }
         else if(strcmp(words->word, newWord->word) < 0){
                insertWord(words->right, newWord);
                }
          else if(strcmp(words->word, newWord->word) > 0){
                insertWord(words->left, newWord);                  
         }*/
         
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Code:
        if(words == NULL){
                 return words;
                  
         }
    should be
    Code:
        if (words == NULL) {
            return newWord;   
        }
    .
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jul 2007
    Posts
    2

    Thumbs up Thanks so much.

    Quote Originally Posted by iMalc View Post
    should be
    Code:
        if (words == NULL) {
            return newWord;   
        }
    .
    I can't believe I spent so long and missed such a little mistake. Really appreciate it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM