#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    27
    Rep Power
    0

    Initializing a tree?


    So basically, I wrote a code but when I try to add a new node to the tree, the node is lost.

    Code:
    struct node{
        int d;
        struct node * right;
        struct node * left;
        struct node * parent;
    };
    Code:
    void insert(node * root, int data){
        node * s1, * s2;
        node * p = malloc(sizeof(node));
        if(!p) return;
    
        p->right = NULL;
        p->left = NULL;
        p->d = data;
    
        if(!root){
            p->parent = NULL;
            root = p;
            printf("**%d**\n", root->d); /* At this point, the root is printed, wich should happen only once*/
            return;
        }
    
        else{
            s1 = root;
            while(s1){
                s2 = s1;
                if(s1->d > data) s1 = s1->left;
                else if(s1->d < data) s1 = s1->right;
                else if(s1->d == data) {free(p); return;}
            }
            p->parent = s2;
            if(s2->d > data) s2->left = p;
            else s2->right = p;
        }
    }
    Then:
    Code:
    int main(){
        node * root = NULL;
    
    //Irrelevant code
       repetition{
          insert(root,num);
       }
    //Irrelevant code
    return 0;
    }
    The insert function is wrong or I'm passing something wrong during the main function? Basically, everytime I add a new node, it goes into the root of the tree, wich means the root is being NULL after the end of the insert function being executed by the repetition. Confirmed this by trying to print root->d in the main function after the insertion, and the program crashed.

    Edit: Just realized I used quotes instead of code tags.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,928
    Rep Power
    481
    To change the value of in one function of that in another you need its address. In other words, if you want to change the pointer to root in main you need to pass its address to insert, and you need to work with that address within insert.
    Code:
    void insert(node**root, int data) {
      node * s1, * s2;
      node * p = malloc(sizeof(node));
      if(!p) return;
      p->right = NULL;
      p->left = NULL;
      p->d = data;
      if(NULL == *root) {
        p->parent = NULL;
        *root = p;
        printf("**%d**\n", (*root)->d); /* At this point, the root is printed, which should happen only once*/
        return;
      } else {
    /*...*/
    }
    int main() {
      node * root = NULL;
      int num;
      for (num = 0; num < 3; ++num)
        insert(&root,num);
      return 0;
    }
    Caveat: my untested codes usually don't work. You showed an incomplete program, I provide an incomplete answer.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    27
    Rep Power
    0
    Originally Posted by b49P23TIvg
    To change the value of in one function of that in another you need its address. In other words, if you want to change the pointer to root in main you need to pass its address to insert, and you need to work with that address within insert.
    Code:
    void insert(node**root, int data) {
      node * s1, * s2;
      node * p = malloc(sizeof(node));
      if(!p) return;
      p->right = NULL;
      p->left = NULL;
      p->d = data;
      if(NULL == *root) {
        p->parent = NULL;
        *root = p;
        printf("**%d**\n", (*root)->d); /* At this point, the root is printed, which should happen only once*/
        return;
      } else {
    /*...*/
    }
    int main() {
      node * root = NULL;
      int num;
      for (num = 0; num < 3; ++num)
        insert(&root,num);
      return 0;
    }
    Caveat: my untested codes usually don't work. You showed an incomplete program, I provide an incomplete answer.
    Don't worry about the program itself, I just needed the information on how to solve it. I kinda knew it was a pointer problem, but wasn't realizing how to fix it.

    Just tested some simple cases and it's working now. Thank you.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    27
    Rep Power
    0
    Oh, and a last question, if I free a node, does the pointers pointing at it become NULL?

    Example(not sure if I was clear): parent->left = p, then I free(p), does parent->left become NULL?
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,928
    Rep Power
    481
    We look up "man free" on the internet, aggressively removing "man freefalls".
    The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed.
    Yes sir, it says nothing about changing memory in space that legitimately belongs to your program.

    However, setting to NULL the value of freed pointers NULL is such a great idea that my personal c toolbox includes a wrapper on free that sets the pointer to NULL. If I compile without turning off debugging then of course my allocation and free routines display their activity and I can check for memory leak.
    Code:
    void dwlfree(void**memory) {
      if ((NULL == memory) || (NULL == *memory)) {
        DEBUG_CODE(fputs("    dwlfree(null)\n",stderr);)
        return;
      }
      DEBUG_CODE(fprintf(stderr,"    dwlfree address %p\n",*memory);)
      free(*memory);
      *memory = NULL;
    }
    Which still isn't the same as updating pointers to that spot from other locations!
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo