C++ AVL 트리 반복자가 제대로 증가하지 않습니다.

Question

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) { } 
}; 

내 반복자는 다음과 같습니다 : 다음과 같이 내 AvlTree 노드는

 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에서, link[0] 및 link[1]에 대한 left 및 right 대체) 작동 : 첫째, end()이의 오른쪽 노드를 찾을 필요가 없습니다 지금까지 코드에 관한 한

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; 
} 

반환 주문 : iterator(NULL); 나무를 보지 않고 그냥 돌려 줄 수 있습니다.

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

그리고 :

는

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

    } 

나는 NULL 포인터 역 참조를 시도하고 있습니다 플래그 첫 번째 줄은 변경되어야합니다

는

알고리즘의 실제 오류는 그러나 여기에 보인다 두 번째 것은 다음과 같습니다.

temp = temp->parent; 

또한 내 코드에서 followi 지금은 수퍼맨입니다. 그것은 제거 될 수 있고, 고정 된 나머지 코드에 의해 똑같은 방식으로 처리 될 것입니다. 또한 위와 같은 동일한 NULL 포인터 역 참조로 인해 어려움을 겪습니다.

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