class iterator
{
protected:
friendclass AvlTree<Comparable>;
AvlNode * node;
AvlNode * findInOrderSuccessor(AvlNode * & t)
{
AvlNode * temp;
//node has a right child
// so successor is leftmost node of right subtree
if(t->right != NULL)
{
temp = t->right; //go right
//go all the way left
while(temp->left != NULL)
{
temp = temp->left;
}
return temp;
}
//node has no right child
//if we are someone's left child, go up one
if(t->parent->left == t)
{
//return your parent
temp = t->parent;
return temp;
}
//if we are someone's right child, go up until the current node
//is someone's left child, then go up one more
temp = t->parent;
while(temp->parent->left != temp)
{
temp = temp->parent; //go up
}
//return your parent
temp = t->parent;
return temp;
}
public:
iterator(AvlNode * p) : node(p)
{ }
//overload * to make *iterator return the element of its node
Comparable & operator*()
{ return node->element; }
iterator operator++ (int) //postfix operator
{
node = findInOrderSuccessor(node);
return iterator(node);
}
// == comparison overload
booloperator==(iterator & rhs)
{ return node == rhs.node; }
// != comparison overload
booloperator!=(iterator &rhs)
{ return node != rhs.node; }
};
As public members of my AVL Tree class, I have included iterator begin() and iterator end(), which point to the leftmost node and one past rightmost node, respectively. While my code compiles, the iterators don't seem to work at all. If I try to print just *tree.begin(), it will print nothing, instead of the expected Comparable element (in this case, a string). Am I doing something improperly?
Nothing really jumps out at me as far as causing that behavior. Does tree.begin() point to a node with an empty string element?
Your postfix operator++ is wrong in that it should return an iterator to the current object instead of the next one.
I don't see any reason to pass the parameter to findInOrderSuccessor by reference and it doesn't really make sense for the container class to be a friend.