Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Binary tree problem...not adding to child nodes (http://www.go4expert.com/forums/binary-tree-problemnot-adding-child-t19735/)

davidelias16 10Oct2009 19:37

Binary tree problem...not adding to child nodes
 
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);
 */    }
   
    }
  }


xpi0t0s 10Oct2009 22:31

Re: Binary tree problem...not adding to child nodes
 
Please read the posting guidelines.
In particular you should have used code tags - this preserves formatting which makes code a lot easier to read.

davidelias16 10Oct2009 23:01

Re: Binary tree problem...not adding to child nodes
 
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);
 */        }
       
    }
  }


davidelias16 10Oct2009 23:03

Re: Binary tree problem...not adding to child nodes
 
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);
 */        }
       
    }
  }


shabbir 11Oct2009 09:16

Re: Binary tree problem...not adding to child nodes
 
Oops. Done it for you as well.


All times are GMT +5.5. The time now is 07:13.