Thread: 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 .

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.