Binary trees in C++ using references

Question

I wish to implement a binary tree using references instead of using pointers (which is generally what you tend to find in every book and every website on the internet). I tried the following code:

class tree_node {
private:
    tree_node& left;
    tree_node& right;
    data_type data;
public:
    void set_left(tree_node&);
    // ... other functions here
};

void tree_node::set_left(tree_node& new_left) {
    this.left = new_left;
}

I get the following error: error C2582: 'operator =' function is unavailable in 'tree_node'.

I know I can easily implement it using pointers but I would like to keep my solution elegant and free of pointers. Can you tell me where I am going wrong?

Answer 1

You can't change the object that a reference refers to¹; once you initialize a reference, it always refers to the object with which it was initialized.

You should use pointers. There is nothing wrong with using pointers for this (it's clean using pointers as well because parent nodes own their children, so cleanup and destruction is easy!)

^{(1) Well, you could explicitly call the object's destructor and then use placement new in the assignment operator implementation, but that's just a mess!}

Answer 2

You cannot assign to references. What you're trying to do can't be done... without a huge amount of bending.. (you'd essentially destroy a node and create a new one each time you want to modify it.)

There's a good reason why all those other people use pointers.

Answer 3

References in C++ don't work the same as references in other languages. Once a reference is set, at construction time, it can't be changed to anything else.

Answer 4

References aren't just pointers with shorter syntax. They're another name for the actual object they refer to, even when used as the lhs of an assignment.

int i = 3;
int j = 4;
int &ref = i;
ref = j;
std::cout << i << "\n"; // prints 4: i itself has been modified, 
                        // because semantically ref *is* i

That is, ref = j has the same effect as i = j, or the same effect as *ptr = j, if you had first done int *ptr = &i;. It means, "copy the contents of the object j, into whatever object ref refers to".

For the full lifetime of ref, it will always refer to i. It cannot be made to refer to any other int, that is to say it cannot be "re-seated".

The same is true of reference data members, it's just that their lifetime is different from automatic variables.

So, when you write this.left = new_left, what that means is, "copy the contents of the object new_left into whatever object this.left refers to". Which (a) isn't what you mean, since you were hoping to re-seat this.left, and (b) even if it was what you meant, it's impossible, since this.left has reference members which themselves cannot be reseated.

It's (b) that causes the compiler error you see, although (a) is why you should use pointers for this.

Answer 5

My recommendation is to use boost's shared_ptr class instead of a reference. This will free you of the concern for managing the pointer's deallocation. You may also be interested in Boost's graph library.