Need to copy Binary Trees

[Orphious]

Stu, I am a little confused thinking about the logic of this. This is what I am suppost to do, perhaps you can help me with it.

Do a preorder traversal, copying nodes as you go. You'll need two functions because the traversals are recursive.

Copy Constructor: BST(const BST & original)
It simply passes the originals root(or all of the original) and root( as a reference parameter) to a recursive function CopyTree() that will do the traversal and node copying, passing the root of the copy back to root.

this means make a constructor
BST(//data)
{ CopyTree(//with those two parameters); } // I guess I'm not getting the root and root part. I would post all the code but its kinda large. Thanks stu

[Stu]

Sorry for not getting back to you sooner, but I've been pretty busy w/ work. Now, on to your question.

I'm going to just cover the logic of a preorder traversal. That seems to be what you aren't understanding. Basically, you process the current node, then all the leafs to the left, and then all the leafs to the right recursively. That means, we will process the left side of the tree on the way down and the right side on the way up, then when we do the right half, we process the same way as the left. This is pretty messy, so I'd like to attack this from a C-like perspective, as it is much more clear.

Assume a node is defined as:

struct myNode {

  struct myNode *left;   // Pointer to the left node/leaf
  int            data;   // The data
  struct myNode *right;  // Pointer to the right node/leaf

};

typedef struct myNode MY_NODE; // Definition of the type
typedef MY_NODE *MY_NODE_PTR;  // Definition of a pointer to the type defined above

I'll assume you have something similar, that you know how to populate it with data, and are aware that when a pointer to a leaf is NULL that you have reached the end of a particular branch.

Now, with that simple understanding. Here's how a preorder traversal would look in a C-like style:

void preorder(MY_NODE_PTR my_tree){

  // See if there is a leaf to process...
  if (my_tree != NULL){ 

    // There is a node...

    // Process data here...
    cout << my_tree->data << '\n' << ends; // For demo, we'll just print it

    // Deal with this node's leafs recursively; first left, then right...
    preorder(my_tree->left);
    preorder(my_tree->right);

  }  // End if 

}  // End preorder()

This is a fairly easy topic once you understand the fundamentals of it. Now, when you pass a reference to the class that you are copying the current class to, hopefully you have a well thought out insert method. All you need to do is insert the current node into the other class in its entirety. This will probably seem like a nightmare, because you are constructing the left side first and the right on the way up. Without seeing how your class is constructed, there is little that I can help you with as to the specifics. However, if you thought of most of the operations that are used in a binary tree and implemented them in your class, this will be a snap to do.

[Orphious]

Stu,
I should of been more specific. I understand the essentials of a preorder, inorder, and postorder. I already did functions to do those traversals. The leafs are defined as follows
DataType data;
BinNode * left,
* right;

typedef BinNode * BinNodePointer;

You assumed correctly that the list can be populated and such, but what I am not understanding is the root root part. Where you call the constructor which calls the CopyTree()

like this:
template <typename DataType>
inline BST<DataType>::BST(const BST & original)
{
CopyTree(root, ptr);// These two parameters are what is passed, the original the and new list.
}

The part I am not understanding is the passing of variables to copytree(). It says to pass the "originals root(or all of the original) and root( as a reference parameter)".

Copytree looks like this
template <typename DataType>
void BST<DataType>::CopyTree(BinNodePointer ptr, BinNodePointer &root)// <---- this stuff
{

if original is empty
set root of new to 0
else
{
get new node for root that contains data in original's root.
CopyTree(pass original left, pass new left);
CopyTree(pass original right, pass new right);
}
}

when I call copy tree, I get originals root, but what are they talking about when they say "and root (as a reference parameter.) Do they mean root of the new one cause I don't think there is one yet. Or do they mean pass root of original twice, just once as a reference. That make sense? b\c I have just confused the hell outta myself . If makes no sense, I'll give it to you verbatim as its written.

[Stu]

Okay, I get you now. Then the parameters are in fact the current node that you are processing (in the instance the copy constructor is being called by) and the node that you wish to populate in the instance that you are copying to (you called it original, but it would be better named copy_to). Basically, you will traverse the nodes in the one and build it in the other. Let's say you have a tree (keeping it simple):

     a
    / \
   /   \
  b     c
 / \   / \
d   e f   g

Using preorder it will be tranversed: a, b, d, e, c, f, g. Therefore, you will pass it, the first time it is called a pointer to root in the instance and a pointer to root in the one that you are copying to. Inside the method you will pass it the left of the instance and the left of the one you are copying to, then the right... This much you seem to have a fairly decent grasp of.

As for the "reference", they mean the address of the leaf (a.k.a pointer or reference to it depending on the type that you are dealing with). But, this is really a non-issue, because it is already just that--a pointer. So, the phrasing of the problem lead you to over-thinking the obvious, per-se.

[Orphious]

One more quick ? stu. I figured out the copy from what you said, but now I am suppost to overload the assignment operator( = )
. It has same structure of copy constructor with 3 significant difference.

1. It must be concerned with self-assignment: object = object.
2. For current_obj = a_diff_obj, the value of current_obj should be destroyed to prevent a memory leak before copying a_diff_obj into current_obj.
3. It has a return type - BST & in this case - and must return the current object( namely itself). This is accomplished by returning *this.

This wording is messing me up again. Do you understand what they are asking?

Thanks again stu.

[Stu]

1. It must be concerned with self-assignment: object = object.

This you use the same method as the copy, provided they are both the same objects with the same class (you used a template).

2. For current_obj = a_diff_obj, the value of current_obj should be destroyed to prevent a memory leak before copying a_diff_obj into current_obj.

Everything except the root node can be destroyed, the root node can be "reset" (data=NULL, left=NULL, right=NULL). Or, you destroy everything and delete the root node and assign it a 'new' root node.

In this case, however, you need to anticipate the classes/types that a_diff_obj can be--which can be a chore.

3. It has a return type - BST & in this case - and must return the current object( namely itself). This is accomplished by returning *this.

Yes, and no. It has a return type of BST<DataType> &. So, BST<string> & and BST<int> & will be two different things.

[Orphious]

Hmm.........i'm still not following. This crap is confusing

I want to overload the = too, so could it be like this? Overloading thing has confused me a bit as well

template <typename ElementType>
inline ostream & operator = (ostream & out, const BST & aBST, const BST & bBST) //where aBST, bBST are the two thing being assigned. Does it matter what you call them here?
{
}

do you need to ostream stuff like you do with the << operator? Sorry for so many questions stu

[Stu]

You only assign one thing to be sent to the ostream, aBST or bBST. If you want to send both, then you would do it like this:

cout << aBST << bBST;

Which is logically equivalent to:

cout << aBST;
cout << bBST;

So, the method will be called twice. Something like this will do:

template <class ElementType> 
inline ostream & BST<ElementType>::operator<<(ostream & out, const BST<ElementType> & aBST) {

  // Do stuff.

  return out;

}

Also, I noticed you aren't prefixing the function with 'BST<ElementType>::'. If it is inside the definition (class BST { ... here ...};), then the 'inline' is not necessary. The default for member functions prototyped and defined in the class definition is inline.

[Orphious]

I want to overload the assignment operator = , thats what I was asking with the aBST and bBST. Thanks for the other info though

[Stu]

Then why are you sending it to an ostream & ? Sending stuff to an ostream is usually done with operator<<(), if you send it via operator=() it will be confusing for anyone who uses your class--because they won't expect it to work like that...

[Orphious]

Copied from an << and forgot to change. sorry. Was just asking about =. Didn't remove the ostream stuff. my bad

[Stu]

Overloading isn't really that complex. Basically, you create one or more member functions (methods) or functions that have the same name, but a different parameter list. When you call the function, the compiler looks for the function that has the parameters that match the ones you pass into it. Example:

#include <string>
#include <iostream>

int myFunction(char *);
int myFunction(string &);

int myFunction(char *){ return 1; }
int myFunction(string &){ return 2; }

int main(int argc, char **argv){

  string myString = "my string";

  return myFunction(myString);  // myFunction(string &) is called

}  // End main()

It is important to note, that the return type is NOT a factor in which function is called. Example:

#include <string>
#include <iostream>

int  myFunction(char *);
char myFunction(string &);

int  myFunction(char *){ return 1; }
char myFunction(string &){ return 2; }

int main(int argc, char **argv){

  string myString = "my string";

  return myFunction(myString);  // myFunction(string &) is called

}  // End main()

And this will throw an error and not compile (because it cannot figure out which one is which):

#include <string>
#include <iostream>

int  myFunction(string &);
char myFunction(string &);

int  myFunction(string &){ return 1; }
char myFunction(string &){ return 2; }

int main(int argc, char **argv){

  string myString = "my string";

  return myFunction(myString);

}  // End main()

With that in mind, the operator=() is no different than any other function. So, you would have the following functions for the scenerios in your earlier post:

// object = object (use 'this' to refer to self; and return '*this' -- it returns to itself)
inline BST<ElementType> & BST<ElementType>::operator=(BST<ElementType> & other_bst);

// object = different object (use 'this' to refer to self; and return '*this' -- it returns to itself)
inline BST<ElementType> & BST<ElementType>::operator=(vector<int> &);
inline BST<ElementType> & BST<ElementType>::operator=(string &);
inline BST<ElementType> & BST<ElementType>::operator=(unsigned int);

// Above parameters for example purposes only.

In addition, when using operator=() in the instance you are always going to 'return *this;'. This may seem weird, but it isn't really. The operator=() is always going to operate on the righthand side of the expression and assign a value to the lefthand side (namely, the class itself). So, it is VERY unlikely that you will ever overload an operator=() in a class and return anything except *this.

[Orphious]

So that "*this" stuff is just saying it will take the righthand, assign it to the lefthand and return the lefthand or *this?

[Stu]

Pretty much. It's just returning itself to itself after it performed the operations in the function.

[Orphious]

well that doesn't seem to complicated. They must just word it in a confusing way to throw me off on purpose. Once again, thanks a bunch stu. I should just put that in my sig, I am saying it so much