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で出力するのではなく、ツリーの最初のorder itemの無限ループを取得します。私はなぜそれが最初の項目を過ぎて移動していないのか分かりません。

Answer 1

次の反復コード（my AVL treeから; link[0]とlink[1]ためleftとrightに置き換え）作品：

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) 

そして、もう1つは

temp = temp->parent; 

また、あなたは私のコードから、今はすごいです。それは削除することができ、（固定された）残りのコードによってまったく同じように処理されます。また、私はちょうど上に指摘した同じNULLポインタ逆参照を苦しんでいます。

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