Reseting root

This is a discussion on Reseting root within the C Programming forums, part of the General Programming Boards category; Hi, I'm taking words from an unknown amount of documents and adding them to a tree. I have a problem ...

  1. #1
    Registered User
    Join Date
    Dec 2003
    Posts
    11

    Unhappy Reseting root

    Hi,
    I'm taking words from an unknown amount of documents and adding them to a tree. I have a problem in my insert function, though, and it keeps reseting root everytime a new word needs to be added to the tree. Maybe it's because I've been staring at it too long, but I don't see why once the root gets the first word it doesn't iterate down the tree. I put in print statements to see where it gets to, but it never enters the else statement.
    Can anyone point it out to me?

    Here's the function:
    Code:
    wordnode_t *insert_node(wordnode_t *root, wordnode_t *nodeptr, wordnode_t *current)
    {
    
    if(root==NULL)
        {
          printf("if i stop here, root not made\n");
          root=nodeptr;
    
             printf("making root in theory. Root is %s, %d\n", root->string, root->counter);
              root->right=NULL;
             root->left=NULL;
        }
      else
        {
          printf("else statement\n");
          current=root;
    while(current!=NULL)
            {
    
          if (strcmp(nodeptr->string, current->string) == 0)
            {
              printf("were in equal to\n");
              nodeptr->counter ++;
                   }
    
            else {
              if(strcmp(nodeptr->string, current->string)>0)
                { printf("were in greater than\n");
                  nodeptr->counter++;
            current=current->right;
             }
    
            if(strcmp(nodeptr->string, current->string)<0)
              {
                printf("were in less than\n");
             nodeptr->counter++;
           current=current->left;
           }
             }
        }
           }
    }
    Any clues appreciated, thanks!

  2. #2
    Welcome to the real world
    Join Date
    Feb 2004
    Posts
    50
    How are you calling the fuction?

  3. #3
    Registered User
    Join Date
    Dec 2003
    Posts
    11
    I'm calling it within a switch statement- where as long as words are coming in, this is implemented.
    Code:
     switch (num)
          {
          case WORD: printf("WORD worked\n"); //instead of case 1, just preference.
              nodeptr=createnode(); //malloc space for the node
              strcpy(nodeptr->string, newword); //copy stuff into node
            insert_node(root, nodeptr, current); //calling the function
            break;
          default:
                 printf("default case\n");
            break;
          }
        }

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Um...you don't put the new node in the tree when you find a place. Try this:
    Code:
    wordnode_t *insert_node(wordnode_t *root, wordnode_t *nodeptr)
    {
      if(root==NULL)
      {
        printf("if i stop here, root not made\n");
        root=nodeptr;
        printf("making root in theory. Root is %s\n", root->string);
        root->right=NULL;
        root->left=NULL;
      }
      else
      {
        wordnode_t *current=root;
        wordnode_t **save = &root;
        while(current!=NULL)
        {
          if (strcmp(nodeptr->string, current->string) == 0)
          {
            printf("were in equal to\n");
          }
          else {
            if(strcmp(nodeptr->string, current->string)>0)
            {
              printf("were in greater than\n");
              save = & current->right;
              current=current->right;
            }
            else if(strcmp(nodeptr->string, current->string)<0)
            {
              printf("were in less than\n");
              save = & current->left;
              current=current->left;
            }
          }
        }
        *save = nodeptr;
        nodeptr->left = NULL;
        nodeptr->right = NULL;
      }
      return root;
    }
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Dec 2003
    Posts
    11
    Thanks, but it's still reseting root to be the new word each time, unfortunately. It never gets to the else statement even using this.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >but it's still reseting root to be the new word each time
    Because you're not calling the function properly. For the function to make changes to the root in main you must either save the return value (as in the code I gave you) or accept a pointer to a pointer as an argument. Here is some test code for you to play around with. Notice how the insert_node function is called:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct n {
      char string[100];
      struct n *left, *right;
    } wordnode_t;
    
    wordnode_t *insert_node(wordnode_t *root, wordnode_t *nodeptr)
    {
      if(root==NULL)
      {
        printf("if i stop here, root not made\n");
        root=nodeptr;
        printf("making root in theory. Root is %s\n", root->string);
        root->right=NULL;
        root->left=NULL;
      }
      else
      {
        wordnode_t *current=root;
        wordnode_t **save = &root;
        while(current!=NULL)
        {
          if (strcmp(nodeptr->string, current->string) == 0)
          {
            printf("were in equal to\n");
          }
          else {
            if(strcmp(nodeptr->string, current->string)>0)
            {
              printf("were in greater than\n");
              save = & current->right;
              current=current->right;
            }
            else if(strcmp(nodeptr->string, current->string)<0)
            {
              printf("were in less than\n");
              save = & current->left;
              current=current->left;
            }
          }
        }
        *save = nodeptr;
        nodeptr->left = NULL;
        nodeptr->right = NULL;
      }
      return root;
    }
    
    void print_node ( char *value, int level )
    {
      int i;
    
      for ( i = 0; i < level; i++ )
        printf ( "\t" );
      printf ( "%s\n", value );
    }
    
    void print_tree_structure ( struct n *node, int level )
    {
      if ( node == NULL )
        print_node ( "~", level );
      else {
        print_tree_structure ( node->right, level + 1 );
        print_node ( node->string, level );
        print_tree_structure ( node->left, level + 1 );
      }
    }
    
    int main ( void )
    {
      wordnode_t *root = NULL;
      wordnode_t *word;
      char buff[BUFSIZ];
    
      while ( fgets ( buff, sizeof buff, stdin ) != NULL ) {
        word = malloc ( sizeof *word );
        strcpy ( word->string, buff );
        root = insert_node ( root, word );
        print_tree_structure ( root, 0 );
        printf ( "\n--------------------\n" );
      }
    }
    What was the current parameter for btw? I saw no real use for it so I removed it in my example.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Dec 2003
    Posts
    11
    root = insert_node ( root, word );
    Thanks! That's why it kept reseting. As to current, I want to do it as following. I have a new node, if there is no root, that new node is now root. If there is a root, I set current equal to it and compare the newnode to current. Depending if newnode is greater than current, I set the current to equal the right branch of where it currently is. If that makes sense. Current is just so I can iterate down the tree, and as long as it doesn't point to null, it iterates.
    I'm going to play around with this code in my comparison functions now. Thanks for your help!

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Current is just so I can iterate down the tree, and as long as it doesn't point to null, it iterates.
    There's no point in making it a function parameter though. You make it a local variable in insert_node and save your self the hassle of dealing with another variable in main (like in the example I gave you ).
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pointer confusion
    By Blackroot in forum C++ Programming
    Replies: 11
    Last Post: 09-12-2007, 12:44 AM
  2. Really basic string operation
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-28-2005, 04:18 PM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 08:10 AM
  4. 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
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM

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