Я реализовал итератор класса внутри своего класса 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;
Вместо того, чтобы выводить все слова в дереве строк по порядку, я получаю бесконечный цикл первого по порядку элемента в дереве. Кажется, я не могу понять, почему он не будет двигаться дальше первого элемента.
end
кажется таким же, какreturn iterator(NULL);
. Я бы предложил добавить множество вывода трассировки в вашу функциюfindInOrderSuccessor
и посмотреть, где ее поведение отличается от того, что должно быть. (Кстати, есть большая вероятность, что проблема в том, что древовидная структура повреждена. Поэтому также записывайте значения указателя и убедитесь, что узел не является своим собственным левым узлом или что-то в этом роде.) - person David Schwartz   schedule 07.03.2012AvlNode * findInOrderSuccessor(AvlNode * & t)
? Почему вы переписали оператор*
и как вы его используете? - person Matteo   schedule 07.03.2012AvlNode * findInOrderSuccessor(AvlNode * & t)
предназначен для того, чтобы взять элемент AvlNode итератора, найти упорядоченный преемник узла и вернуть итератор, указывающий на него. Оператор*
предназначен для разыменования, поэтому*itr
даетelement
узла итератораitr
. - person Netsuki   schedule 07.03.2012++
мне ясно, чего я не понимаю, так это почему вы переписали оператор*
, не могли бы вы просто использовать стандартный оператор разыменования? Потому что, переписывая его, становится трудно (по крайней мере для меня) интерпретировать, какой аргумент вы передаете функцииfindInOrderSuccessor(AvlNode * & t)
, что, на мой взгляд, может привести к ошибкам суммирования... - person Matteo   schedule 07.03.2012*
перегружен только в отношении объекта итератора. Скажем, у меня естьiterator itr
, если я затем скажу*itr
, он вернетComparable element
узла, на который указывает itr. КодAvlNode * & t
просто передает ссылку на указатель AvlNode и не имеет отношения к оператору итератора*
- person Netsuki   schedule 07.03.2012