Copying a binary tree.

I'm trying to implement a tree and I would like to have some way to make a deep copy of the trees, but I can't seem to make it work.

I have a base class 'Node' from which two other classes inherit from, the 'Leaf' and 'Point classes. A leaf class children can be of either type 'Leaf' or 'Point'.

Anyway, here's the code:

Here's the 'Node' base class:

Code:

class Node {
	public:
		virtual double Get() const = 0;
	
		virtual ~Node() {}
};

The 'Leaf' class:

Code:

class Leaf : public Node {
	private:
		Node *left;
		Node *right;
		
		friend Node *cp(Node *);
		
	public:
		Leaf(Node *left, Node *right);
		~Leaf();
	
		double Get() const;
};

Leaf::Leaf(Node *left, Node *right) : left(left), right(right) {}

Leaf::~Leaf() {
	delete left;
	delete right;
}

double Leaf::Get() const {
	return this->left->Get() + this->right->Get();
}

The 'Point' class:

Code:

class Point : public Node {
	private:
		double value;
		
	public:
		Point(const double &param);
		Point(const Point &param);
		~Point();
	
		double Get() const;
		
		Point &operator = (const Point &rhs);
};

Point::Point(const double &param) : value(param) {}
Point::Point(const Point &param) : value(param.value) {}
Point::~Point() {}

double Point::Get() const {
	return this->value;
}

Point &Point::operator = (const Point &rhs) {
	this->value = rhs.value;
	
	return *this;
}

The main function:

Code:

int main() {
	Point *a = new Point(2.0);
	Point *b = new Point(4.0);
	Point *c = new Point(6.0);
	Point *d = new Point(8.0);
	Point *e = new Point(10.0);
	Point *f = new Point(12.0);
	Point *g = new Point(14.0);
	Point *h = new Point(16.0);
	
	Leaf *i = new Leaf(a, b);
	Leaf *j = new Leaf(c, d);
	Leaf *k = new Leaf(e, f);
	Leaf *l = new Leaf(g, h);

	std::cout << "Copy or Segfault?" << std::endl;
	Node *m = cp(i);
	Node *n = cp(j);
	Node *o = cp(k);
	Node *p = cp(l);
	std::cout << "Copy!" << std::endl;
	
	delete i;
	delete j;
	delete k;
	delete l;
	
	std::cout << "Did it work?" << std::endl;
	std::cout << m->Get() << std::endl;
	std::cout << n->Get() << std::endl;
	std::cout << o->Get() << std::endl;
	std::cout << p->Get() << std::endl;
	std::cout << "Yepp" << std::endl;
	
	return 0;
}

And the function where I try to copy the tree recursively, obviously it dosn't work. The functionality that this function provides I would like to later implement in the 'Node', 'Leaf' and 'Point' classes respectively:

Code:

Node *cp(Node *orig) {
	Node *copy;
	
	if(typeid(orig) == typeid(Leaf *)){
		copy = new Leaf(cp((dynamic_cast<Leaf *>(orig)->left)),
				cp((dynamic_cast<Leaf *>(orig)->right)));
	} else {
		copy = new Point(*(dynamic_cast<Point *>(orig)));
	}
	
	return copy;
}

Any help would be appreciated .

Your design is way off to begin with, I'd say. For example, leaves don't have children - that's the definition of a leaf node! Your Leaf class should be Branch or something, and Point should be Leaf. The whole polymorphic approach to trees is wrong, too. It's far too much hassle to insert new nodes if it often means that you have to replace a leaf with a branch. And there's the overhead, the ugly RTTI lookups, all that. It's far better to have just a simple node class with pointers to the children, and simply set those pointer to null if there aren't any children.


OK, now for the actual problem in your code, it's that you're using typeid incorrectly. To see if orig pointer to a leaf, you have to do

Code:

if(typeid(*orig) == typeid(Leaf))

And that's still the wrong approach. You never do a typeid check and follow it up with an equivalent dynamic_cast. What you do is this:

Code:

if(!orig) {
  copy = 0;
} else if(Leaf *lorig = dynamic_cast<Leaf *>(orig)) {
  copy = new Leaf(cp(lorig->left), cp(lorig->right));
} else {
  // Can only be Point
  copy = new Point(*static_cast<Point*>(orig));
}

But as I said, this is all wrong.

The easiest way would be to implement a copy constructor. Inside that function, simply traverse the original tree (any order should do), adding each node that is visited to the new tree.

Originally Posted by MacNilly

The easiest way would be to implement a copy constructor. Inside that function, simply traverse the original tree (any order should do), adding each node that is visited to the new tree.

Be wary though that when dealing with Binary Trees, order definitely matters. I could have two different trees each containing the values:

Code:

1 2 3 4 5 6 7 8 9 10

but depending on the order in which those values were added to the tree, they could be structured completely differently. If you're going to implement a copy constructor/assignment operator, remember that the "values" contained are not as important as the actual "structure" of the tree. It's the structure you want to remain in tact when you copy/assign it. If you can get the structure copied right, then naturally the values contained will also be correct (granted you copy the data as you copy the structure).

To solve this problem, think first how you might "display" the tree to the command line. Once you can do that, it should seem much clearer how to implement copying.