An interested student inquires: > Hey Dr. Kraemer, i was wondering if u could take a look at my header file for the TreeNode and see if it's correct. > > Thanks, > XXX > > > #ifndef TREENODE_H > #define TREENODE_H > > > template class Bin= > STree; > > template class TreeNode { > = > > friend class DLL ; > = > > public: > TreeNode(const T &v): Left(NULL), Data(v), Right(NUL= > L) { } > TreeNode(const T &v,const TreeNode &l): Left(l), Data(v= > ), Right(NULL) { } > TreeNode(const T &v,const TreeNode &l,const= > TreeNode &r): Left(l), Data(v), Right(r) { } > private: > Tre= > eNode *Left; > TreeNode *Right; > T Data; > }; > > #endi= > f > > -------ff61119c4ca9401522e62bf8cdfff374-- EK replies: Hi, Sorry for the slow reply. I assume you've been able to sort this out already, but here goes ... These: TreeNode *Left; TreeNode *Right; really need to be: TreeNode *Left; TreeNode *Right; and you need to add: // BinTree needs access to left and right friend class BinSTree; ek ----------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------------------------------------- An (intermingled) inquiry and reply: > > Dr. Kraemer, > I had a few questions about project 2. > > 1. What do we have to do differently for the protected methods from the binstree class? Nothing really. You might want to extend this class to create some specialized classes later. Making them protected allows the subclasses to directly access what they need to. > > 2. Why do we need a CopyTree method and a copy constructor for the binstree class? CopyTree takes a pointer to TreeNode as an input parameter. In more advanced types of trees, you might want to do "tree rotations" -- this will make use of that. The copy constuctor takes a BinSTree as an input parameter. You can call CopyTree from inside this constructor and then set the root and size for the tree. > > 3. The signature for the FindNode method is TreeNode *FindNode(const T& item, TreeNode* &parent) const. Why is there a * after TreeNode and an & before parent? Arghhh! That should really read: TreeNode *FindNode(const T& item, TreeNode* &parent) const; which locates a node with a data item and its parent in a tree (used by Find and Delete) The browser interpreted the as a tag ... Sorry. The "&" parameters indicate that this is pass-by-reference ... > > 4. At the end of the FindNode method, you say "used by Find and Delete." Does this mean that DeleteTree uses FindNode? If so, what is the other method that uses FindNode? Is it CopyTree? > It is used by "Delete", not by "DeleteTree" ... In Delete, an item value is passed in, we call FindNode and it returns a pointer to either the node that contains or "where it should be" if it were in the tree. The "Find" method also uses "FindNode"... ek > 5. When printing a horizontal version of the tree, would you rather it look like this: > . > .. > . > ... > . . > ... > . > .. > . > where the rightmost leaf is on the top line, the root on the middle line, and the leftmost leaf on the bottom line, or like this: > .... > ... > .. > .. > . > . > . > . > where the root and all rightmost nodes are on the first line and the leftmost leaf is on the last line? I'll post some examples now ... > > 6. To overload the assignment operator, could we simply clear one tree then copy the other into it? To overload the assignment operator: *) check if you're trying to copy a tree to itself *) clear the current tree *) copy the new tree, assigning the returned pointer to root *) set the size > > 7. Why do we need both FindNode(item, parent) and Find(item)? Find applies to the current tree FindNode applies to a particular subtree. The parent variable is set by FindNode, pointing to the parent of the node containing the value, or the node that would be the parent of the node containing "item" (if it were in the tree). Find uses FindNode > > 8. What is the difference between ClearTree and DeleteTree? Is it that ClearTree maintains the root, whereas DeleteTree does not? DeleteTree does the work of recursing down through the tree, delete nodes ( using FreeTreeNode) on the way back up. ClearTree calls DeleteTree and then sets the root to NULL. > > 9. The signature for Update is: void Update(constT& item). Should there be a space between const and T? Yes, sorry about that. > > 10. I'm confused about the Update method. > To which data value do we need to compare the "current" node? Update calls FindNode, which leaves current pointing to the node with the searched-for value if it is there, and set to NULL if the value is not there. The parent pointer is left pointing to the parent of the current node (if is is there) or to the place where it should be (if not already in the tree). You compare it to the value that was passed in. > Why wouldn't it be defined? If it does not exist, where in the tree does it need to be inserted? It is isn't in the tree. At the place where it *would* be, if it were in the tree. The parent pointer is left pointing to the parent of the place where it should be ... > > 11. One of the protected data members for the binstree is "an integer indicating its size." Is this the size of the most current pointer or the size of the tree? number of elements in the tree > > 12. The description for the Find method includes: "which leaves current pointing at the node matching the data item." What does this mean? :-) "current" is a marker. You search for a node with a particular value. If you find it, current is pointing there. If you don't find it, current is NULL. The parent pointer is left pointing to the parent of the current node (if is is there) or to the place where it should be (if not already in the tree). ek > > Thanks so much for your help! > - xxx > -------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------ > > Hi Dr. Kraemer, its xxx from data structures. I'm having trouble with the leafcount and the depth functions... any suggestions on where to start? i was going to use one the scans for the leafcount and check each node if the right and left are null, but that doesn't work b/c of the function pointer passed in. > > Thanks for any suggestions, > xxx > Hi, Ask me about these in class today ... ek -------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------ > > In the BinSTree class, could you tell me more about the level parameter > for the PrintTree function and the dataWidth and screenWidth parameters > for the PrintVTree function? Also, why do we need to overload the > assignment operator? > Hi, I'll go over this in class today. ek -------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------ > > I am a little confused about the functions: > TreeNode *CopyTree(TreeNode *t) > which creates a duplicate of tree t and returns > a new root > void DeleteTree (TreeNode *t) > which dealloates the memory occupied by a tree > > They're supposed to deal with trees, but they take in tree nodes. Do we > have to traverse through the tree, starting at the root? Can we, by any > chance, use the in-order, pre-order, or post-order traversal functions? > Hi, That should be: // used by copy constructor and assignment operator TreeNode *CopyTree(TreeNode *t); and // used by destructor, assignment operator and ClearList void DeleteTree(TreeNode *t); ... the didn't show up in the html pages ... sorry Yes, you traverse the tree ... if t is NULL, you've reached a leaf. Then, check the left and right children. If they're non-null .. copy them and link them in to the current node. Taking in pointers to TreeNodes allows them to operate recursively ... ek -------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------ > > > > Dr. Kraemer, > > > > I've been working on Project #2's TreeNode class for a while, but I'm stuck at the compiling step. The getter functions return a pointer to the left/right child, right?? > > > > //this is the line that is in my .h file > > TreeNode* getLeftChild(); > > > > //this is the line that is in my .cpp file > > template > > TreeNode* TreeNode::getLeftChild() > > { > > .... > > } > > > > These lines throw a compiler error that says, "expected constructor, destructor, or type conversion before * token" and "expected ; before * token". The same thing happens for getRightChild(). Is there something wrong in my function signature? > > > > Thank you and have a great weekend! > > XXX > > return TreeNode * rather than TreeNode * ek -------------------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx------------------