tree copy constructor...

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

my node class looks like this....

Code:

---

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

Code:

---

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

Code:

---

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
  }

};

---

Quote:

---

Originally Posted by georgi0u

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:

Code:

---

  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

i did do that...

sorry i didn't post this before.

Code:

---

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

Code:

---

  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; 
  }

---

Quote:

---

Originally Posted by georgi0u

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:

Code:

---

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:

Code:

---

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

---

Also expect this to work:

Code:

---

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

---

since both are natural means of assigning and constructing objects.

Regards,

Paul McKenzie