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