tree copy constructor...

[georgi0u]

can anyone see any issues with this copy constructor for a binary tree data structure...

my node class looks like this....

template <class T>
class TreeNode {
public:
  TreeNode() : left(0), right(0),parent(0) {}
  TreeNode(const T& init) : value(init), left(0), right(0),parent(0) {}
  T value;
  TreeNode* left;
  TreeNode* right;
  TreeNode* parent;
 
};

and my copy constructor looks like this...

  TreeNode<T>*  copy_tree( TreeNode<T>* old_root )
  {
	TreeNode<T> *p = new TreeNode<T>;
	TreeNode<T> *q = new TreeNode<T>;
	
	p->value = old_root->value;
	if(old_root->parent)
		q->value = old_root->parent->value;
	else
		q = 0;
	p->parent = q;
	
	if(old_root->left)
		p->left = copy_tree(old_root->left);
	if(old_root->right)
		p->right = copy_tree(old_root->right);
	
	return p;  
  }

i have a working increment operator my my iterator class and for some reason trees that were formed via my copy constructor don't iterate correctly, so i'm thinking i have some sort of a memory mismanagement.

any ideas?

thanks
-adam



heres my iterator class for anyone who thinks they need it to diagnose my issue...

template <class T>
class tree_iterator {
public:
  friend class cs2set<T>;
private:
  TreeNode<T>* ptr_;
public:
  tree_iterator() : ptr_(0) {}
  tree_iterator( TreeNode<T>* p ) : ptr_(p) {}
  tree_iterator( const tree_iterator& old ) : ptr_(old.ptr_) {}
  ~tree_iterator() {}
  
  tree_iterator& operator=( const tree_iterator& old )
  { ptr_ = old.ptr_;  return *this; }
  
  //  operator* gives constant access to the value at the pointer
  const T& operator*() const
  {
    return ptr_->value;
  }

  //  Comparions operators are straightforward
  friend bool operator== ( const tree_iterator& lft, const tree_iterator& rgt )
  { return lft.ptr_ == rgt.ptr_; }
  
  friend bool operator!= ( const tree_iterator& lft, const tree_iterator& rgt )
  { return lft.ptr_ != rgt.ptr_; }


  //--------------------------------------------------
  //  HW 8:  Two ++ and two -- operators
  //--------------------------------------------------

  //  HW 8:  pre-increment
  tree_iterator<T> & operator++( ) 
  {  
	if(ptr_->right){
		ptr_ = ptr_->right;
		while(ptr_->left) ptr_ = ptr_->left;
		return *this;
	}
	else {
		while(ptr_->parent && ptr_->parent->right && ptr_->parent -> right == ptr_ ) ptr_=ptr_->parent;
		if(ptr_->parent)
			ptr_ = ptr_->parent;
		else
			ptr_ = 0;
		return *this;
	}
  }

  //  HW 8:  post-increment is indicated by the dummy int argument
  tree_iterator<T> operator++( int ) 
  {
    tree_iterator<T> temp( *this ); 	
	if(ptr_->right){
		ptr_ = ptr_->right;
		while(ptr_->left) ptr_ = ptr_->left;
		return *this;
	}
	else {
		while(ptr_->parent && ptr_->parent->right && ptr_->parent -> right == ptr_ ) ptr_=ptr_->parent;
		if(ptr_->parent)
			ptr_ = ptr_->parent;
		else
			ptr_ = 0;
		return *this;
	}
	
    return temp;   // return what was the current iterator
  }

  //  HW 8:  pre-decrement
  tree_iterator<T> & operator--( ) {
	if(!ptr_->left) {
	while(ptr_->parent && ptr_ -> parent->left && ptr_->parent->left == ptr_) ptr_ = ptr_ -> parent;
		if(ptr_->parent)
			ptr_ = ptr_->parent;
		else
			ptr_ = 0;
		return *this;
	}
	else {
		ptr_ =ptr_->left;
		while(ptr_->right) ptr_ = ptr_ -> right;
		return *this;
	}
  }
 
  //  HW 8:  post-decrement is indicated by the dummy int argument
  tree_iterator<T> operator--( int ) 
  {
    tree_iterator<T> temp( *this ); // save an iterator referencing the current node
	if(!ptr_->left) {
	while(ptr_->parent && ptr_ -> parent->left && ptr_->parent->left == ptr_) ptr_ = ptr_ -> parent;
		if(ptr_->parent)
			ptr_ = ptr_->parent;
		else
			ptr_ = 0;
		return *this;
	}
	else {
		ptr_ =ptr_->left;
		while(ptr_->right) ptr_ = ptr_ -> right;
		return *this;
	}
    return temp;   // return what was the current iterator
  }

};

[Paul McKenzie]

can anyone see any issues with this copy constructor for a binary tree data structure...

Before anything, have you used the debugger to see what your problems may be?

Second:

  TreeNode<T>*  copy_tree( TreeNode<T>* old_root )

This is not a copy constructor. It is function called copy_tree(). Please show your true copy constructor. If it calls copy_tree(), still show the real copy constructor.

Third, implementing a copy constructor means you should implement a user-defined assignment operator and proper destructor. Did you do that?

Regards,

Paul McKenzie

[georgi0u]

i did do that...

sorry i didn't post this before.

template <class T>
class cs2set {
public:
  typedef tree_iterator<T> iterator;

private:
  TreeNode<T>* root_;
  int size_;

public:
  cs2set() : root_(0), size_(0) 
  {}

  cs2set( const cs2set<T>& old ) : size_(old.size_) {
	this ->destroy_tree(root_);
    root_ = this -> copy_tree( old.root_,0 );
  }

  ~cs2set()  {
    this -> destroy_tree( root_ );
    root_ = 0;
  }

anyway im posting this for future referance because i already figured it out. The problem was with the way i was dealing with node parents...

heres the revised working version of what my copy constructor calls....

  TreeNode<T>*  copy_tree( TreeNode<T>* old_root,TreeNode<T>* tempparent ) {
	if(!old_root) return 0;
	TreeNode<T> *p = new TreeNode<T>;
	p->value = old_root->value;
	p->parent = tempparent;
	
	if(old_root->left)
		p->left = copy_tree(old_root->left,p);
	if(old_root->right)
		p->right = copy_tree(old_root->right,p);
	
	return p;  
  }

[Paul McKenzie]

Anyway im posting this for future referance because i already figured it out. The problem was with the way i was dealing with node parents...

You still didn't code an assignment operator. If not, your program will not be able to do this correctly:

int main()
{
   TreeNode<int> T1;
   TreeNode<int> T2;

   T1 = T2;   // no good
}

When coding a copy constructor, it always goes with an assignment operator. The reason why is that C++ programmers who expect this to work:

TreeNode<int> T1;
TreeNode<int> T2 = T1; // copy constructor called

Also expect this to work:

   TreeNode<int> T1;
   TreeNode<int> T2;
   T1 = T2;

since both are natural means of assigning and constructing objects.

Regards,

Paul McKenzie