Unable to store string's into my Binary Search Tree?

This is a discussion on Unable to store string's into my Binary Search Tree? within the C Programming forums, part of the General Programming Boards category; This is my first time really resorting to asking for help online, I have been able to handle most of ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    9

    Unable to store string's into my Binary Search Tree?

    This is my first time really resorting to asking for help online, I have been able to handle most of my programming projects by myself until now.

    I am required to make a binary search tree that will read in a dictionary of words (from a text file I designate).

    I am having some errors however in actually storing the words into my BST.

    I get error C2106 = left operand must be l-value for the line "
    Code:
      p->data = malloc(strlen(value) + 1);
    and
    Code:
      strcpy(p->data, value);
    will cause my program to crash upon reaching this point.

    Code:
    /* Structure Definition
    struct treeNode {
     char data[20];
     struct treeNode *left;
     struct treeNode *right;
    };
    */
    // The following is the main part of the function that reads in each word and attempts to store it to the BST.
    
    if ((filePtr = fopen (fileName, "r"))== NULL)
    		printf ("Sorry the file could not be opened. \n");   // Attempts to open the file.
    	else
    	{
    		while (!feof (filePtr))
    		{
    			fgets(buffer, 20,  filePtr);
    			printf ("%s", buffer);
    			treeNode_insert(root, buffer);
    		}
    	}
    // This last bit is the actual insert, but this is where I am having the errors.
    
    struct treeNode *treeNode_insert(struct treeNode *p, char value) {
     struct treeNode *tmp_one = NULL;
     struct treeNode *tmp_two = NULL;
     int resultforTemp1;
     int resultforTemp2;
    
     if(p == NULL) {
      /* insert [new] treeNode as root node */
      p = (struct treeNode *)malloc(sizeof(struct treeNode));
      p->data = malloc(strlen(value) + 1); // Throws errors.
      strcpy(p->data, value);  // Throws errors.
      p->left = p->right = NULL;
     } else {
      tmp_one = p;
      /* Traverse the tree to get a pointer to the specific treeNode */
      /* The child of this treeNode will be the [new] treeNode */
      while(tmp_one != NULL) 
      {
       tmp_two = tmp_one;
        resultforTemp1 = strcmp (tmp_one->data, value);
       if(resultforTemp1 > 0)
        tmp_one = tmp_one->left;
       else
        tmp_one = tmp_one->right;
      }
    resultforTemp2 = strcmp(tmp_two->data, value);
      if(resultforTemp2 > 0) 
      {
       /* insert [new] treeNode as left child */
       tmp_two->left = (struct treeNode *)malloc(sizeof(struct treeNode));
       tmp_two = tmp_two->left;
       strcpy(tmp_two->data, value);
    //   tmp_two->data = value;
       tmp_two->left = tmp_two->right = NULL;
      } else {
       /* insert [new] treeNode as left child */
       tmp_two->right = (struct treeNode *)malloc(sizeof(struct treeNode)); 
       tmp_two = tmp_two->right;
       strcpy(tmp_two->data, value);
       // tmp_two->data = value;
       tmp_two->left = tmp_two->right = NULL;
      }
     }
     return(p);
    }

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    This fails
    Code:
    p->data = malloc(strlen(value) + 1);
    because data is a char array, not a pointer. The malloc expects a pointer. Since you've allocated a char array already, there's no need to malloc some heap for it.

    If you want to malloc heap for it, then change the definition in your struct to
    Code:
    char * data ;
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    That worked, and made it compile again, however it will still read in the first line of the dictionary, and upon reaching the strcpy it will crash =(

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Variable "value" is defined as a single char value. Is it really a null terminated string?
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    What do you mean? My concept was to fgets a line from the dictionary (which using printf it will grab the first word correctly) and then pass it to the node insert.

    Do you mean in my function declaration where I have
    Code:
    struct treeNode *treeNode_insert(struct treeNode *p, char value);
    ?

    If so, how would I be able to change that to handle the situation, make an array or another pointer?

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    ok, changed it to an array doing char value[], and it started adding my list, prolly went through about 1,000 words and caused an assertion failure, but i'll try and figure that one out.

    Thanks for the help though! That one simple question got me to looking at my code differently lol

  7. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    So my program will go through the entire dictionary I supply, but when I attempt to print out the "tree" it fails to print.

    In an attempt to debug it, I step into the function treeNode_insert.

    For some reason, every iteration it ONLY hits this part of the function. Why is p always being null, if everytime I am saving a variable to it?
    Code:
    if (p == null)
     {
      /* insert [new] treeNode as root node */
      p = (struct treeNode *)malloc(sizeof(struct treeNode));
      p->data = malloc(strlen(value) + 1);
      strcpy(p->data, value);
      p->left = p->right = NULL;
    }

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    I'm good, but I'm not that good. You'll have to post some more code - in and around where you call the routine to print.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    Ok, my loop to go through the dictionary and "add" is
    Code:
    do 
    	do 
    		{
    			fgets(buffer, 20,  filePtr);
    			printf ("%s", buffer);
    			treeNode_insert(root, buffer);
    		} while (!feof (filePtr));
    treeNode_insert that is being called everytime. The one thing that I am not 100% sure about, is my insertion function is returning a pointer to a node, however I am continuously calling (root) in the loop to get through my dictionary. Maybe this has something to do with it?

    Code:
    struct treeNode *treeNode_insert(struct treeNode *p, char value[]) 
    {
    	
            struct treeNode *tmp_one = NULL;
    	struct treeNode *tmp_two = NULL;
    	int resultforTemp1;
    	int resultforTemp2;
    
    	if(p == NULL) 
    	{
    		/* insert [new] treeNode as root node */
    		p = (struct treeNode *)malloc(sizeof(struct treeNode));
    		p->data = malloc(strlen(value) + 1);
    		strcpy(p->data, value);
    		p->left = p->right = NULL;
    	} 
    	else 
    	{
    		tmp_one = p;
    		/* Traverse the tree to get a pointer to the specific treeNode */
    		/* The child of this treeNode will be the [new] treeNode */
    		while(tmp_one != NULL) 
    		{
    			tmp_two = tmp_one;
    			resultforTemp1 = strcmp (tmp_one->data, value);
    			if(resultforTemp1 > 0)
    				tmp_one = tmp_one->left;
    			else
    				tmp_one = tmp_one->right;
    		}
    		resultforTemp2 = strcmp(tmp_two->data, value);
    		if(resultforTemp2 > 0) 
    		{
    			/* insert [new] treeNode as left child */
    			tmp_two->left = (struct treeNode *)malloc(sizeof(struct treeNode));
    			tmp_two = tmp_two->left;
    			strcpy(tmp_two->data, value);
    			//   tmp_two->data = value;
    			tmp_two->left = tmp_two->right = NULL;
    		} else {
    			/* insert [new] treeNode as left child */
    			tmp_two->right = (struct treeNode *)malloc(sizeof(struct treeNode)); 
    			tmp_two = tmp_two->right;
    			strcpy(tmp_two->data, value);
    			// tmp_two->data = value;
    			tmp_two->left = tmp_two->right = NULL;
    		}
    	}
    	return(p);

    My tree print
    Code:
    void print_tree (struct treeNode *p)
    {
    	print_node (p);
    	if (p->left != NULL) print_tree(p->left);
    	if (p->right != NULL) print_tree (p->right);
    }
    
    void print_node (struct treeNode *p)
    {
    	if (p==NULL)
    	{
    		printf ("Empty top\n");
    		return;
    	}
    	printf ("The word is %s", p->data);
    }
    Last edited by twiztidsoulz; 11-03-2009 at 11:39 AM. Reason: Cleaned up indentation on code.

  10. #10
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Every time you malloc a treenode for p, and you return it, it goes into the bit bucket. I suspect you might want to assign it to root instead.

    Also, indenting only 1 character makes your code hard to follow.

    And, each time you enter your insert function, you will only need to malloc once to create the new node. You have 3 mallocs there. I would have structured my code with two functions:

    node * create_a_node(...) ;
    node * insertNode(node * anode, ...) ;

    But, you can certainly have the insertNode function create the node.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    I'm always trying to get people to separate their allocation of a node from its insertion into the data structure, so I highly recommend it.

    All you need to do is to think about what the return value of treeNode_insert is for, what it is supposed to return, and what the caller is meant to do with that?
    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"

  12. #12
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    So to make sure I understand this, the return value of treeNode_insert is a pointer to a node (p). Root in the main function should be a pointer to the "root" of the search tree, which I then pass to treeNode_insert as (p).

    In insertNode, I am then checking/adding the new node, and then returning the pointer of (p) with the new node added to it as a child, with p still at the root.

    I still can't figure out why I can't actually add to my binary search tree.

    Assuming that is all correct, I pass in a NULL root node. Since it is null, I assign a new node at the root, and then set the left and right children to NULL. Return the pointer.

    On the next iteration, root should now be passed through with a value at the head, and then check to see whether the value I am passing through is higher or lower than the root's value.

    The only thing I can currently think of, is add a temporary variable that stores the return value of (treeNode_insert) and consequently set root = to that temp value.

  13. #13
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    Just did some debugging to see what happens, the p->data is being saved correctly, for example if the word that is read from the dictionary is "sitting" for example, that is being passed and stored correctly, however the left and right children always say "Unable to evaluate this expression.

    This is so confusing, but I really appreciate the insight you have given so far.

  14. #14
    Registered User
    Join Date
    Nov 2009
    Posts
    9
    Got my BST working, and storing the entire dictionary, thank you so much for the insight on how to fix it!

  15. #15
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Good deal.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. parent in a binary search tree
    By roaan in forum C Programming
    Replies: 4
    Last Post: 08-26-2009, 07:08 PM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. Searching a binary search tree - doesn't work
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-11-2005, 03:53 PM
  4. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21