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; 

而不是输出字符串树中的所有单词inorder，我得到树中的第一个订单项的无限循环。我似乎无法弄清楚为什么它不会移过第一项。

Answer 1

下一次迭代的代码工作（从my AVL tree;替换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; 

    } 

我标记可尝试空指针引用，而第一行应改为：

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

而第二个到：

temp = temp->parent; 

另外，你可能已经注意到我的代码，followi ng现在超级富有;它可以被移除，并且将通过（固定的）剩余代码以完全相同的方式处理。它也遭受了我上面指出的相同的NULL指针解引用。

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