BST에 대한 이터레이터 늘리기

Question

어떻게 제대로 처리 할 수 ​​있을지 모르지만 템플릿을 사용하는 이진 검색 트리 클래스에서 이터레이터를 증가시킬 수 있어야합니다.

반복자의 구조에는 현재 노드뿐만 아니라 현재 위치를 정의하는 정수가 있습니다. 내가 가지고있는 유일한 문제는 ++Iter 작업을 수행 할 때 오른쪽 또는 왼쪽으로 이동해야하는지 여부를 어떻게 결정해야합니까? 나는 포트에 내가 가진 예외를 사용할 수 없습니다 생각 안드로이드 NDK,이 코드를 많이 계획하기 때문에 나는이에 대한 예외를 사용할 수 없습니다

template < typename TComparable, typename TValue > 
    class SearchTree 
    { 
    public: 
     class Iterator; 
    private: 
     struct Node; 
     typedef typename Node TNode; 
    public: 
     SearchTree(void); 
     ~SearchTree(void); 
    public: 
     TValue find(const TComparable& k); 
     TValue find(int32_t index); 
     TValue find(const Iterator& pIter); 

     Iterator begin(void) const; 
     Iterator end(void) const; 

     void insert(const TComparable& k, const TValue& v); 
     void insert(const Iterator& pIter); 

     friend class Iterator; 
     friend class TNode; 
    private: 
     int32_t mNodeCount; 
     TNode* mRoot; 
    public: 
     class Iterator 
     { 
     public: 
      Iterator(void); 
      Iterator(int32_t position); 
      ~Iterator(void); 
      inline TNode* operator->(void) const 
      { return mCurrentNode; } 
      void operator++(void); 
      bool operator==(const Iterator& pIter); 
      bool operator!=(const Iterator& pIter); 
     private: 
      int32_t getNumStepsLeftToLeaf(void); 
      int32_t getNumStepsRightToLeaf(void); 
      bool isLeafNode(const Node*& n); 
      bool isInternalNode(const Node*& n); 
     private: 
      TNode* mCurrentNode; 
      int32_t mIterPosition; 
      friend class TNode; 
     }; 
    private: 
     struct Node 
     { 
     public: 
      Node(void) : mParent(NULL), mLeftChild(NULL), mRightChild(NULL) 
      {} 
      ~Node(void) 
      { 
       if (mParent) delete mParent; 
       if (mLeftChild) delete mLeftChild; 
       if (mRightChild) delete mRightChild; 
      } 
      int32_t index; 
      TComparable Key; 
      TValue Value; 
      TNode* mParent; 
      TNode* mLeftChild; 
      TNode* mRightChild; 
     }; 
    }; 

참고 : 여기에

는 전체 클래스의 헤더 파일입니다 STLport (내가 사용하는 것입니다 - GnuSTL은 GPL입니다. 이것은 내가 이익을 위해 무엇을 하는지를 의미합니다) 나는 그것을 사용할 수 없습니다 - 누군가가 그것을 모순하는 것이 있다면 알려주세요)

또한 누구나 부스트에 대해 언급하기 전에 이미 NDK로 포팅을 시도했습니다. 인생을 훨씬 쉽게 만들어주기 때문에 그것을 사용하고 싶습니다만, 지금은 자신의 데이터 구조와 알고리즘을 기꺼이 쓸 것입니다.

이터레이터에 관한 한, 필자는 여기서 내 디자인에 뭔가 빠져있는 것 같아요. 그리고 누구든지 이것이 무엇인지 알면 알려주세요. 나는 누군가가 그것을 필요로한다면 이것에 대한 전체 수업 자료를 게시하게되어 기쁘다.

모든

Answer 1

첫째, 접두사 증가 연산자는이 서명이 있습니다

Iterator& operator++(); 

을하고 후위 선언이 방법으로 접두사의 관점에서 정의되어야한다 :

const Iterator& operator++(int){Iterator old = *this; ++(*this); return old;} 

당신은 아마 원하는 그 노드에 다음 (가장 왼쪽) 노드에게 물어볼 접두사

Iterator& Iterator::operator++(){ 
    myParent = mCurrentNode; 
    return myParent.getRightOf(mCurrentNode); 
} 

나는 당신은 적어도 사적인 노드가 있어야하는 노드로부터 반복자를 만드는 방법이 있다고 가정합니다.

리프 노드를 반복하려고한다고 가정합니다 (어쨌든 내부 노드 구현은 비슷하지 않습니다). 당신은 다음을 수행 더 많거나 적은 getRightOf 방법이 필요, 내가 그것을 위해 어떤 의사를 적어 보자

Node* Node::getRightOf(Node* aNode){ 
    if aNode == mLeftChild{ 
     if mRightNode 
      return mRightNode(this); 
     return mParent(this) 
    } 
    if aNode == mRightChild{ 
     return mParent(this) 
    } 
    if aNode == mParent{ 
     if mLeftNode 
      return mLeftNode(this); 
     if mRightNode 
      return mRightNode(this); 
     return this; 
    } 
} 

당신은 용기의 끝 부분에 반복과 같은 경우를 관리하기위한 몇 가지주의가 필요합니다.

경고 노드의 소멸자에서

내가 읽어

if (mParent) delete mParent; 

이 위험 같습니다 누가 인 parentNode를 삭제? 왼쪽 또는 오른쪽 자식?