What does *& mean in C?

Question

I was new to the concepts of trees. I was studying Serialization and deSerialization. I got a example program from a link, copied it, and executed it. It ran, but when I tried to understand it, I could not understand one line - void deSerialize(Node *&root, FILE *fp)

Why is *& mean?

The whole code is:

#include <stdio.h>
#define MARKER -1

/* A binary tree Node has key, pointer to left and right children */
struct Node
{
int key;
struct Node* left, *right;
};

/* Helper function that allocates a new Node with the
given key and NULL left and right pointers. */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}

// This function stores a tree in a file pointed by fp
void serialize(Node *root, FILE *fp)
{
// If current node is NULL, store marker
if (root == NULL)
{
    fprintf(fp, "%d ", MARKER);
    return;
}

// Else, store current node and recur for its children
fprintf(fp, "%d ", root->key);
serialize(root->left, fp);
serialize(root->right, fp);
}

// This function constructs a tree from a file pointed by 'fp'
void deSerialize(Node *&root, FILE *fp)
{
// Read next item from file. If theere are no more items or next
// item is marker, then return
int val;
if ( !fscanf(fp, "%d ", &val) || val == MARKER)
   return;

// Else create node with this item and recur for children
root = newNode(val);
deSerialize(root->left, fp);
deSerialize(root->right, fp);
}

// A simple inorder traversal used for testing the constructed tree
void inorder(Node *root)
{
if (root)
{
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}
}

/* Driver program to test above functions*/
int main()
{
// Let us construct a tree shown in the above figure
struct Node *root        = newNode(20);
root->left               = newNode(8);
root->right              = newNode(22);
root->left->left         = newNode(4);
root->left->right        = newNode(12);
root->left->right->left  = newNode(10);
root->left->right->right = newNode(14);

// Let us open a file and serialize the tree into the file
FILE *fp = fopen("tree.txt", "w");
if (fp == NULL)
{
    puts("Could not open file");
    return 0;
}
serialize(root, fp);
fclose(fp);

// Let us deserialize the storeed tree into root1
Node *root1 = NULL;
fp = fopen("tree.txt", "r");
deSerialize(root1, fp);

printf("Inorder Traversal of the tree constructed from file:\n");
inorder(root1);

return 0;
}

Any help appreciated.

Answer 1

The *& is not a single symbol. But a combination of two:

* for a pointer. & for reference.

So you have the function:

void deSerialize(Node *&root, FILE *fp)

This function first parameter is a reference to a Node pointer.

Meaning - when using it you send it a Node * object. And the function itself can change this pointer value - since you passed it by reference.

This allows you to allocate memory inside the function.

A different way to write this function would be:

Node *deSerialize(Node *root, FILE *fp)

And use it differently ofcourse:

root->left = deSerialize(root->left, fp)

See full solution here: http://ideone.com/5GzAyd. And relevant part:

Node *deSerialize(Node *root, FILE *fp)
{
    // Read next item from file. If theere are no more items or next
    // item is marker, then return
    int val;
    if ( !fscanf(fp, "%d ", &val) || val == MARKER)
       return NULL;

    // Else create node with this item and recur for children
    root = newNode(val);
    root->left = deSerialize(root->left, fp);
    root->right = deSerialize(root->right, fp);
    return root;
}

Answer 2

In C?

It means nothing and will give you syntax error.

In C++?

It is a reference to the pointer.

Node *&root. So its

 Node*  which is the Node pointer
 & root where  root is reference variable  

Note that this is in C++ and not C.

Also you can check a related thread: What does *& in a function declaration mean?

Answer 3

You can read it as

Node* &root

It is simply a reference to a pointer variable. You need it because there may be a case where your root is empty and you need to change its value.
You can achieve it by using pointer to pointer too ie.

 Node **root

But there are advantages with references-

Once a reference is initialized to refer to an object, it can not be changed to refer to another object (with pointer you can always). So, it ensures that you will not change your root to point somewhere else accidently , which is possible if you use pointer to pointer.

Answer 4

I have simple way to understand this

1)we know

int *ptr

this means ptr is pointer to int variable

2)we also know

int &ref

this means ref is reference to int variable

now we replace int in 2) with int *

int* &X

that means X is reference of pointer and pointer points to int variable