Copying a binary tree.

This is a discussion on Copying a binary tree. within the C++ Programming forums, part of the General Programming Boards category; I'm trying to implement a tree and I would like to have some way to make a deep copy of ...

  1. #1
    Registered User nempo's Avatar
    Join Date
    Aug 2007
    Posts
    39

    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 .

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    320
    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.

  4. #4
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by MacNilly View Post
    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.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21