Reputation: 1091
i have written a simple code to create and insert elements into a binary search tree, when i write the code in the following manner, the chaining doesn't seem to happen, can anybody help me understand what exactly is happening in the insert function ? I know the code to insert elements into a binary search tree, just curious to know why this one doesn't work.
#include <stdio.h>
#include<stdlib.h>
struct node {
struct node *left;
struct node* right;
int element;
};
void insert(struct node *node,int x) {
if(node==NULL) {
node=(struct node *)malloc(sizeof(struct node));
node->element=x;
node->left=NULL;
node->right=NULL;
} else {
if(x<node->element) {
insert(node->left,x);}
else {
insert(node->right,x);
}
}
}
void inorder(struct node *base) {
if(base!=NULL) {
inorder(base->left);
printf("%d ",base->element);
inorder(base->right);
}
}
int main(int argc, char *argv[]) {
struct node *base;
base=(struct node *)malloc(sizeof(struct node));
base->element=1;
base->left=NULL;
base->right=NULL;
insert(base,25);
insert(base,30);
inorder(base);
return 0;
}
if the insert function is written this way, it works but still doesn't work for creation of the first node of the binary search tree, confused :/
void insert2(struct node *node,int x) {
if(node==NULL) {
node=(struct node *)malloc(sizeof(struct node));
node->element=x;
node->left=NULL;
node->right=NULL;
} else {
if(x<node->element) {
if(node->left==NULL) {
node->left=(struct node *)malloc(sizeof(struct node));
node->left->element=x;
node->left->left=NULL;
node->left->right=NULL;
} else {
insert2(node->left,x);
}
} else {
if(node->right==NULL) {
node->right=(struct node *)malloc(sizeof(struct node));
node->right->element=x;
node->right->left=NULL;
node->right->right=NULL;
} else {
insert2(node->right,x);
}
}
}
}
Upvotes: 3
Views: 178
Reputation: 1056
C is pass-by-value. When you pass something into a function's parameter, the function makes a copy of it. So when you pass a struct node pointer
into the insert
function, C makes a copy of that pointer.
What you did in main
is first you made a struct node* base
:
base --> struct node
.
When you call insert(base, 25)
, C makes a copy of base. So now in your memory you have something like this:
basecpy ---> [struct node] <--- base
So in your insert
, you are essentially doing
if(basecpy==NULL)
{basecpy=(struct node *)malloc(sizeof(struct node));
basecpy->element=x;
basecpy->left=NULL;
basecpy->right=NULL;}
Which does not change base
in anyway at all - it just changes basecpy
.
This can be solved by using double pointers:
void insert(struct node **node, int x) {
if (*node == NULL) {
*node = malloc(sizeof(*node));
(*node)->element=x;
(*node)->left=NULL;
(*node)->right=NULL;
} else {
if (x < (*node)->element) {
insert(&((*node)->left), x);
} else {
insert(&((*node)->right), x);
}
}
}
And then to use it, pass in the address of base.
insert(&base, 25);
Pointers can be tricky :)
Upvotes: 1
Reputation: 15652
When you pass a value to a function in C, you're using pass-by-value. What that means is the value gets copied into another variable which becomes local to the function.
void change(struct node *n) {
n = 42;
}
int main(void) {
change(NULL); // change can't change the value of NULL, can it?
}
Now take a look at your insert
function... Suppose I call insert(NULL,42);
, do you think insert
is trying to change NULL
? Or is it trying to change some local variable, which your main
function can't see?
You know what needs to be done already... Either make your insert
function use an extra level of pointer indirection as you've suggested in your comments, or return the root node from insert
so that you can propagate the changes made by insert
into the data structure stored in main
(using the assignment =
operator).
Upvotes: 1