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.