C ++ pointers and pointer to reference
I am trying to create a binary search tree. I have used recursive procedures to insert nodes into a tree. The code looks like this.
void BST :: insertRoot(Node* node, int data) {
if (node == NULL)
this -> root = new Node(data);
else
insertOthers(node, data);
}
void BST :: insertOthers(Node* node, int data) {
if(node == NULL) {
node = new Node(data);
return;
}
if(data < node->getData())
insertOthers(node->getLeft(), data);
else
insertOthers(node->getRight(), data);
}
In this code, only one node is inserted into the tree and then the connection is aborted. However, when I change mine Node*
to Node*&
, it works fine. However, I cannot figure out what is the difference between the two. Can anyone explain the differentiation of these two memory cards? Thanks you
source to share
If you take a pointer parameter by value:
Node* node
then changing it:
node = new Node(data);
will change the local variable inside the function; but not the caller argument. This new meaning will be lost and the tree will remain as it was.
Passing by reference (link to pointer, not pointer to link):
Node*& node
means that the local parameter refers to the same pointer as the caller's argument, so the caller will see this change for the new value. So, assuming the rest of the logic is correct, this will update the pointer inside the tree to point to the new node as you want.
source to share
When you pass a pointer by value, the function receives a copy of the pointer as a parameter. You cannot change the original pointer inside a function, because you only have access to a copy.
When you pass a pointer by reference, the original pointer can be changed through the link. This appears to be your intent as otherwise you will be leaking the allocated node.
It may be opinion based, but for better readability I would declare your function like this Node* BST::insertOthers(int data)
and return a pointer to the allocated node.
source to share
The pointer is an integral value. When you pass anything by value, int, double, float, pointer, etc., the function will work on the copy. Changes to the copy are not passed back to the caller.
In short, your problem is no different from this:
void foo(int x)
{
x = 10;
}
int main()
{
int value = 0;
foo(value);
// value is still 0 after the call, not 10
}
Note that value
it hasn't changed even though it was transferred foo
. To fix the problem of reverting changes back to the caller, in C ++ you pass a reference - in the above case, a reference to int
, in your case, a reference to Node*
.
source to share