I was creating a function to insert a element in a binary tree and, first, i did the following on Visual Studio 2012:
void Insert(Nodo *root, int x){
if(root == NULL){
Nodo *n = new Nodo();
n->value = x
root = n;
return;
}
else{
if(root->value > x)
Insert(&(root)->left, x);
else
Insert(&(root)->right, x);
}
}
But this same code doesn't work at Dev-C++, I need to use Pointer of Pointer to make it work, like this:
void Insert(Nodo **root, int x){
if(*root == NULL){
Nodo *n = new Nodo();
n->value = x
*root = n;
return;
}
else{
if((*root)->value > x)
Insert(&(*root)->left, x);
else
Insert(&(*root)->right, x);
}
}
Does anybody knows why it happens?
The first code should not compile. In fact it doesn't compile under MSVC 2013.
Why ?
Your node structure should be something like this:
struct Nodo {
int value;
Nodo*left, *right; // pointer to the children nodes
};
This means that (root)->left
is of type Nodo*
. Hence &(root)->left
is of type Nodo**
which is incompatible with a Nodo*
argument.
Anyway, in your insert function, you certainly want to change the tree. But if you'd for example do: root = n;
you would just update the root argument (pointer). This update is lost as soon as you leave the function. Here, you certainly want to change either the content of the root node or more probably the pointer to a root node.
In the second version, you pass as argument the address of a pointer to a node, and then update this pointer when necessary (expected behaviour).
Remark
The first version could be "saved", if you would go for a pass by reference:
void Insert(Nodo * &root, int x){ // root then refers to the original pointer
if(root == NULL){ // if the original poitner is null...
Nodo *n = new Nodo();
n->value = x
root = n; // the orginal pointer would be changed via the reference
return;
}
else{
if(root->value > x)
Insert(root->left, x); // argument is the pointer that could be updated
else
Insert(root->right, x);
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With