我在 AvlTree 类中实现了一个类迭代器。我的 AvlTree 节点如下:
struct AvlNode
{
Comparable element;
list<int> lines; //line occurrences
bool flag; //checks validity
AvlNode *left;
AvlNode *right;
AvlNode *parent; //parent pointer
int height;
AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, AvlNode *pt,
int h = 0, bool b = true )
: element( theElement ), left( lt ), right( rt ), parent( pt ), height( h ), flag( b ) { }
};
我的迭代器如下:
class iterator
{
protected:
friend class 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
bool operator==(iterator rhs)
{ return node == rhs.node; }
// != comparison overload
bool operator!=(iterator rhs)
{ return !(*this == rhs); }
};
我的 AvlTree 还有一个作为公共成员的开始和结束迭代器:
//begin iterator points to leftmost node
iterator begin()
{ //return pointer to leftmost node
AvlNode *temp = root;
while(temp->left != NULL)
temp = temp->left;
return iterator(temp);
}
//end iterator points to one after rightmost node
iterator end()
{ //return NULL right pointer of rightmost node
AvlNode * temp = root;
while(temp->right != NULL)
temp = temp->right;
return iterator( temp->right );
}
我的问题是,当我尝试在 main 中运行以下命令时:
for(AvlTree<string>::iterator itr = tree.begin(); itr != (tree.end()); itr++)
cout << *itr << endl;
我没有按顺序输出字符串树中的所有单词,而是得到了树中第一个按顺序项的无限循环。我似乎无法弄清楚为什么它不会超过第一项。