Binary tree problem...not adding to child nodes

Discussion in 'C' started by davidelias16, Oct 10, 2009.

  1. davidelias16

    davidelias16 New Member

    Joined:
    Oct 10, 2009
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    My problem seems to be that whenever I call insertintosubtree from itself passing in the new root (next level in the tree), trying to get to the end of the tree it always seems to bring the to pass in the root of the whole tree rather than just the local parent.

    Also when I have finished inserting all the values when I try to print even the first "root.left" word it returns nothing, the tree seems to be completely empty except for the root.
    What am I doing wrong?

    ****************SEARCH.H FILE:*************
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define delims " "
    
    /* each string can contain this may characters */
    #define MAX_STRING_SIZE      30
    
    
    int count;
    
    typedef struct word* WordPtr;
    
    WordPtr root, current, head, newNode, previous, next;
    
    int insertWord(char *inword, int songnum, int wordnum);
    
    
    typedef struct word
    {
       char word[MAX_STRING_SIZE + 1];
       int songnumber;
       int wordnumber;
       int checked;
       WordPtr left; /*points to the left child*/
       WordPtr right; /*points to the right child*/
    } WordType;
    
    
     int InsertIntoSubTree(WordType parent, WordType current);
    
    ****************SEARCH.C FILE:*************
    Code:
    #include "search.h"
    
    /*gcc -ansi -Wall -pedantic -o wordsearch search.c*/
     
    int main(int argc, char **argv){
    
     char *word[30];
     int i;
     int j;
     int k;
     int t;
     FILE *songs;
     char str[3000];
    /*  BSTWort *root = new BSTWord;
     */
    /*  open file */
     songs = fopen(argv[1], "r");
    
     printf("\nPlease be patient while list is populated...\n");
    
      i=0;
     /*  while each line is not empty... */
      while(fgets(str, 3000, songs)!=NULL)
       {
       /* dynamically allocate pointer in matrix[i] with the size of int */
        t=0;
    
        for(k=0; k<strlen(str);k++)
        {
         if (str[k-1] == ' ')
         /*prevent double spacing related errors*/
         if(str[k] != ' ')
         t++;
        }
        
         for(j=0;j<(t+1);j++)/*just for each row*/
          {
           if(j==0) /* if first word */
              {
               strcpy(word, strtok( str, delims ));
               /*  string tokenise line between spaces*/
               insertWord(word, i+1, j+1);
              }
          else
              {
               strcpy(word, strtok( NULL, delims ));
               insertWord(word, i+1, j+1);
              }
           }
         
        i++;
       }
       
       current=root;
    while(current/*  && current->headItem != NULL */){
    printf("%s\n", current);
    current = current->right;
    }
    
        printf("%s", root->word);
        printf("\n%i words successfully inserted into tree!\n\n", count); 
       
        wordsearch();
       
     return EXIT_SUCCESS;
     }
     
     
    /* BST()
    {
    root = NULL;
    }
      */
    int insertWord(char *inword, int songnum, int wordnum)
       {
    /*    BSTWord *newNode=malloc(sizeof(WordType));
     */    int success = 0;
    
    /*     printf("%s-%i-%i, ", inword, songnum, wordnum);
     */
    if( (newNode=malloc(sizeof(WordType))) == NULL)
        {
            fprintf(stderr, "\nMemory Allocation for ListInsert failed!\n");
            fprintf(stderr, "\nAborting data entry!\n");
            exit(1);
        } 
        
        strcpy(newNode->word, inword);
        newNode->songnumber = songnum;
        newNode->wordnumber = wordnum;
        newNode->checked = 0;
        newNode->left = NULL;
        newNode->right = NULL;
        
       if (root == NULL)
        {
            root = newNode;
            count++;
            success = 1;        
            printf("root word: %s\n",root->word);
        }
        else if (root->word == inword)
        {
            return 0;
        }
        else
        {
            success = InsertIntoSubTree(*root, *newNode);
        }
         
    
        
        return success;
    }
    
    /* Insert into the BST sub branch */
    
    int InsertIntoSubTree(WordType parent, WordType current)
    {
        int success = 0;
        int i;
        
    /*              new->nextCategory=current;
     */
        
         if (strcmp(current.word, parent.word)<0)
         {
          printf("less than root...");
          
          if(parent.left != NULL)
          {
           success = InsertIntoSubTree(*parent.left, current);
          }
          else
          {
          parent.left = &current;
          printf("%s", parent.left);
          count++;
          printf("%s inserted to left of %s\n", current.word, parent.word);
          }
         }
         else if(strcmp(current.word, parent.word)>0)
         {
          printf("greater than root...");
          
          if(parent.right != NULL)
          {
           success = InsertIntoSubTree(*parent.right, current);
          }
          else
          {
          parent.right = &current;
          count++;
          printf("%s inserted to right of %s\n", current.word, parent.word);
          }
         }
         else
         {
          printf("same as root\n");
         }
    
        return success;
    }
    
    void wordsearch()
    {
       int pass=0;
       int i=0;
    
      while(pass==0)
      {
        char qword[70];
        printf("Enter a query: \n");
        fgets(qword, 80, stdin);
    
           for(i=0;i<strlen(qword);i++)
                 {
                   if ( qword[i] == '\n' )
                     {
                       qword[i] = '\0';
                       break;
                     }
                 } 
    
    /*        else if((strlen(qword) < 2) || (strlen(qword) > 26))
              {
               if(strlen(qword) == 1)
                 {
               printf("Exiting...\n\n");
                 }
              fprintf(stderr, "Please enter between 1 and 25 characters...\n");
              } */
        
        
         if(*qword=='0')
         {
         printf("Exiting...\n\n");
         pass=1;
         }
         else
         {
    /*      printf("%s", qword); */
         printf("Song  Positions\n");
    /*      findword(root, qword);
     */     }
         
        }
      }
     
    Last edited by a moderator: Oct 11, 2009
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Please read the posting guidelines.
    In particular you should have used code tags - this preserves formatting which makes code a lot easier to read.
     
  3. davidelias16

    davidelias16 New Member

    Joined:
    Oct 10, 2009
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    My apologies for not code tagging previously.
    Here is it again with the code tags in place



    /****************SEARCH.H FILE:*************/
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define delims " "
    
    /* each string can contain this may characters */
    #define MAX_STRING_SIZE      30
    
    
    int count;
    
    typedef struct word* WordPtr;
    
    WordPtr root, current, head, newNode, previous, next;
    
    int insertWord(char *inword, int songnum, int wordnum);
    
    
    typedef struct word
    {
       char word[MAX_STRING_SIZE + 1];
       int songnumber;
       int wordnumber;
       int checked;
       WordPtr left; /*points to the left child*/
       WordPtr right; /*points to the right child*/
    } WordType;
    
    
     int InsertIntoSubTree(WordType parent, WordType current);
    
    
    /****************SEARCH.C FILE:***************/
    Code:
    #include "search.h"
    
    /*gcc -ansi -Wall -pedantic -o wordsearch search.c*/
     
    int main(int argc, char **argv){
    
     char *word[30];
     int i;
     int j;
     int k;
     int t;
     FILE *songs;
     char str[3000];
    /*  BSTWort *root = new BSTWord;
     */
    /*  open file */
     songs = fopen(argv[1], "r");
    
     printf("\nPlease be patient while list is populated...\n");
    
      i=0;
     /*  while each line is not empty... */
      while(fgets(str, 3000, songs)!=NULL)
       {
       /* dynamically allocate pointer in matrix[i] with the size of int */
    	t=0;
    
    	for(k=0; k<strlen(str);k++)
    	{
    	 if (str[k-1] == ' ')
    	 /*prevent double spacing related errors*/
    	 if(str[k] != ' ')
    	 t++;
    	}
    	
    	 for(j=0;j<(t+1);j++)/*just for each row*/
    	  {
    	   if(j==0) /* if first word */
              {
    		   strcpy(word, strtok( str, delims ));
    		   /*  string tokenise line between spaces*/
    		   insertWord(word, i+1, j+1);
              }
    	  else
    	      {
    		   strcpy(word, strtok( NULL, delims ));
    		   insertWord(word, i+1, j+1);
    	      }
     	  }
    	 
    	i++;
       }
       
       current=root;
      while(current)
      {
      printf("%s\n", current);
      current = current->right;
      }
    
        printf("%s", root->word);
        printf("\n%i words successfully inserted into tree!\n\n", count); 
       
        wordsearch();
       
     return EXIT_SUCCESS;
     }
     
     
    
    int insertWord(char *inword, int songnum, int wordnum)
       {
    
    if( (newNode=malloc(sizeof(WordType))) == NULL)
    	{
    		fprintf(stderr, "\nMemory Allocation for ListInsert failed!\n");
    		fprintf(stderr, "\nAborting data entry!\n");
    		exit(1);
    	} 
    	
    	strcpy(newNode->word, inword);
    	newNode->songnumber = songnum;
    	newNode->wordnumber = wordnum;
    	newNode->checked = 0;
    	newNode->left = NULL;
    	newNode->right = NULL;
    	
       if (root == NULL)
        {
            root = newNode;
    		count++;
            success = 1;        
            printf("root word: %s\n",root->word);
        }
        else if (root->word == inword)
        {
            return 0;
        }
        else
        {
            success = InsertIntoSubTree(*root, *newNode);
        }
         
    
    	
        return success;
    }
    
    /* Insert into the BST sub branch */
    
    int InsertIntoSubTree(WordType parent, WordType current)
    {
        int success = 0;
        int i;
    	
         if (strcmp(current.word, parent.word)<0)
         {
          printf("less than root...");
    	  
    	  if(parent.left != NULL)
    	  {
    	   success = InsertIntoSubTree(*parent.left, current);
    	  }
    	  else
    	  {
    	  parent.left = &current;
    	  printf("%s", parent.left);
    	  count++;
    	  printf("%s inserted to left of %s\n", current.word, parent.word);
    	  }
    	 }
    	 else if(strcmp(current.word, parent.word)>0)
    	 {
          printf("greater than root...");
    	  
    	  if(parent.right != NULL)
    	  {
    	   success = InsertIntoSubTree(*parent.right, current);
    	  }
    	  else
    	  {
    	  parent.right = &current;
    	  count++;
    	  printf("%s inserted to right of %s\n", current.word, parent.word);
    	  }
    	 }
    	 else
    	 {
    	  printf("same as root\n");
    	 }
    
        return success;
    }
    
    void wordsearch()
    {
       int pass=0;
       int i=0;
    
      while(pass==0)
      {
        char qword[70];
        printf("Enter a query: \n");
        fgets(qword, 80, stdin);
    
           for(i=0;i<strlen(qword);i++)
                 {
                   if ( qword[i] == '\n' )
                     {
                       qword[i] = '\0';
                       break;
                     }
                 } 
    
    /*        else if((strlen(qword) < 2) || (strlen(qword) > 26))
    	      {
               if(strlen(qword) == 1)
    		     {
               printf("Exiting...\n\n");
                 }
    		  fprintf(stderr, "Please enter between 1 and 25 characters...\n");
              } */
        
    	
         if(*qword=='0')
    	 {
    	 printf("Exiting...\n\n");
    	 pass=1;
    	 }
    	 else
    	 {
    /* 	 printf("%s", qword); */
    	 printf("Song  Positions\n");
    /* 	 findword(root, qword);
     */	 }
    	 
        }
      }
     
    Last edited by a moderator: Oct 11, 2009
  4. davidelias16

    davidelias16 New Member

    Joined:
    Oct 10, 2009
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Oops, first time sorry about this

    Code:
    ****************SEARCH.C FILE:***************/
    
    #include "search.h"
    
    /*gcc -ansi -Wall -pedantic -o wordsearch search.c*/
     
    int main(int argc, char **argv){
    
     char *word[30];
     int i;
     int j;
     int k;
     int t;
     FILE *songs;
     char str[3000];
    /*  BSTWort *root = new BSTWord;
     */
    /*  open file */
     songs = fopen(argv[1], "r");
    
     printf("\nPlease be patient while list is populated...\n");
    
      i=0;
     /*  while each line is not empty... */
      while(fgets(str, 3000, songs)!=NULL)
       {
       /* dynamically allocate pointer in matrix[i] with the size of int */
    	t=0;
    
    	for(k=0; k<strlen(str);k++)
    	{
    	 if (str[k-1] == ' ')
    	 /*prevent double spacing related errors*/
    	 if(str[k] != ' ')
    	 t++;
    	}
    	
    	 for(j=0;j<(t+1);j++)/*just for each row*/
    	  {
    	   if(j==0) /* if first word */
              {
    		   strcpy(word, strtok( str, delims ));
    		   /*  string tokenise line between spaces*/
    		   insertWord(word, i+1, j+1);
              }
    	  else
    	      {
    		   strcpy(word, strtok( NULL, delims ));
    		   insertWord(word, i+1, j+1);
    	      }
     	  }
    	 
    	i++;
       }
       
       current=root;
      while(current)
      {
      printf("%s\n", current);
      current = current->right;
      }
    
        printf("%s", root->word);
        printf("\n%i words successfully inserted into tree!\n\n", count); 
       
        wordsearch();
       
     return EXIT_SUCCESS;
     }
     
     
    
    int insertWord(char *inword, int songnum, int wordnum)
       {
    
    if( (newNode=malloc(sizeof(WordType))) == NULL)
    	{
    		fprintf(stderr, "\nMemory Allocation for ListInsert failed!\n");
    		fprintf(stderr, "\nAborting data entry!\n");
    		exit(1);
    	} 
    	
    	strcpy(newNode->word, inword);
    	newNode->songnumber = songnum;
    	newNode->wordnumber = wordnum;
    	newNode->checked = 0;
    	newNode->left = NULL;
    	newNode->right = NULL;
    	
       if (root == NULL)
        {
            root = newNode;
    		count++;
            success = 1;        
            printf("root word: %s\n",root->word);
        }
        else if (root->word == inword)
        {
            return 0;
        }
        else
        {
            success = InsertIntoSubTree(*root, *newNode);
        }
         
    
    	
        return success;
    }
    
    /* Insert into the BST sub branch */
    
    int InsertIntoSubTree(WordType parent, WordType current)
    {
        int success = 0;
        int i;
    	
         if (strcmp(current.word, parent.word)<0)
         {
          printf("less than root...");
    	  
    	  if(parent.left != NULL)
    	  {
    	   success = InsertIntoSubTree(*parent.left, current);
    	  }
    	  else
    	  {
    	  parent.left = &current;
    	  printf("%s", parent.left);
    	  count++;
    	  printf("%s inserted to left of %s\n", current.word, parent.word);
    	  }
    	 }
    	 else if(strcmp(current.word, parent.word)>0)
    	 {
          printf("greater than root...");
    	  
    	  if(parent.right != NULL)
    	  {
    	   success = InsertIntoSubTree(*parent.right, current);
    	  }
    	  else
    	  {
    	  parent.right = &current;
    	  count++;
    	  printf("%s inserted to right of %s\n", current.word, parent.word);
    	  }
    	 }
    	 else
    	 {
    	  printf("same as root\n");
    	 }
    
        return success;
    }
    
    void wordsearch()
    {
       int pass=0;
       int i=0;
    
      while(pass==0)
      {
        char qword[70];
        printf("Enter a query: \n");
        fgets(qword, 80, stdin);
    
           for(i=0;i<strlen(qword);i++)
                 {
                   if ( qword[i] == '\n' )
                     {
                       qword[i] = '\0';
                       break;
                     }
                 } 
    
    /*        else if((strlen(qword) < 2) || (strlen(qword) > 26))
    	      {
               if(strlen(qword) == 1)
    		     {
               printf("Exiting...\n\n");
                 }
    		  fprintf(stderr, "Please enter between 1 and 25 characters...\n");
              } */
        
    	
         if(*qword=='0')
    	 {
    	 printf("Exiting...\n\n");
    	 pass=1;
    	 }
    	 else
    	 {
    /* 	 printf("%s", qword); */
    	 printf("Song  Positions\n");
    /* 	 findword(root, qword);
     */	 }
    	 
        }
      }
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Oops. Done it for you as well.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice