Binary tree problem...not adding to child nodes

davidelias16's Avatar, Join Date: Oct 2009
Light Poster
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 shabbir; 11Oct2009 at 09:15.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Please read the posting guidelines.
In particular you should have used code tags - this preserves formatting which makes code a lot easier to read.
0
davidelias16's Avatar, Join Date: Oct 2009
Light Poster
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 shabbir; 11Oct2009 at 09:15.. Reason: Code blocks
0
davidelias16's Avatar, Join Date: Oct 2009
Light Poster
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);
 */	 }
	 
    }
  }
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Oops. Done it for you as well.