Итератор дерева C ++ AVL не будет увеличиваться должным образом

Question

Я реализовал итератор класса внутри своего класса 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 );
}

Моя проблема в том, что когда я пытаюсь запустить в основном следующее:

    for(AvlTree<string>::iterator itr = tree.begin(); itr != (tree.end()); itr++)
        cout << *itr << endl;

Вместо вывода всех слов в порядке следования дерева строк, я получаю бесконечный цикл первого элемента порядка в дереве. Кажется, я не могу понять, почему он не пройдет мимо первого пункта.

Answer 1

Работает следующий итерационный код (из моего дерева AVL ; подставьте left и right для link[0] и link[1]):

BAVLNode * BAVL_GetFirst (const BAVL *o)
{
    if (!o->root) {
        return NULL;
    }

    BAVLNode *n = o->root;
    while (n->link[0]) {
        n = n->link[0];
    }

    return n;
}

BAVLNode * BAVL_GetNext (const BAVL *o, BAVLNode *n)
{
    if (n->link[1]) {
        n = n->link[1];
        while (n->link[0]) {
            n = n->link[0];
        }
    } else {
        while (n->parent && n == n->parent->link[1]) {
            n = n->parent;
        }
        n = n->parent;
    }

    return n;
}

НасколькоВаш код обеспокоен, во-первых, end() не нужно находить самый правый узел для возврата iterator(NULL);он может просто вернуть это, не глядя на дерево.

Фактическая ошибка в вашем алгоритме, однако, выглядит так:

        temp = t->parent;
WRONG:  while(temp->parent->left != temp)
        {
            temp = temp->parent; //go up 
        }
        //return your parent
WRONG:  temp = t->parent;
        return temp;

    }

Первая помеченная мной строка может попытаться разыменовать указатель NULL,и должен быть изменен на:

while(temp->parent && temp->parent->left != temp)

А второй на:

temp = temp->parent;

Кроме того, вы, возможно, заметили из моего кода, что следующее теперь супер;он может быть удален и будет обработан точно таким же образом (фиксированным) оставшимся кодом.Он также страдает от того же разыменования нулевого указателя, на который я указал чуть выше.

//if we are someone's left child, go up one
if(t->parent->left == t)
{
    //return your parent
    temp = t->parent;
    return temp;
}