Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 19th, 2013, 04:44 PM
 VicFS
Registered User

Join Date: Nov 2012
Posts: 26
Time spent in forums: 9 h 24 m 3 sec
Reputation 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
April 19th, 2013, 05:41 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
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!

#3
April 19th, 2013, 06:39 PM
 VicFS
Registered User

Join Date: Nov 2012
Posts: 26
Time spent in forums: 9 h 24 m 3 sec
Reputation Power: 0
Quote:
 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.

#4
April 19th, 2013, 06:47 PM
 VicFS
Registered User

Join Date: Nov 2012
Posts: 26
Time spent in forums: 9 h 24 m 3 sec
Reputation 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?

#5
April 19th, 2013, 07:19 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
We look up "man free" on the internet, aggressively removing "man freefalls".
Quote:
 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;
}
free(*memory);
*memory = NULL;
}```

Which still isn't the same as updating pointers to that spot from other locations!

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Initializing a tree?