BSTのイテレータのインクリメント

Question

私はこれをどうやって正しく行うことができないのか困惑していますが、私が実装しているテンプレートを使用するバイナリ検索ツリークラス内でイテレータをインクリメントできる必要があります。

イテレータの構造は、現在のノード、ならびにその現在位置を規定する整数を有します。私がいる唯一の問題は、私はそれが右に行くか左かどうかを決定する必要がありますどのように、それは++Iter操作を行う際に、ありますか？

ここでは、クラス全体のヘッダファイルです：私はとの例外を使用することはできません信じるのAndroid 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にそれを移植しようとしています。人生をもっと楽にしてくれるように、私はそれを使いたいですが、今のところ自分のデータ構造とアルゴリズムを書くつもりです。

限りイテレータとして、私はここに私のデザインで何かが欠けている推測している、と誰もが、これは何ができるか知っている場合、私に知らせてください。私は誰もがそれを必要とする場合は、このためのクラス全体のソースを投稿することを嬉しく思います。

Iterator& operator++(); 

とPostfixがこのように接頭語の用語で宣言され、定義されるべきである：

Answer 1

まず、前置インクリメント演算子は、この署名を持っている

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

あなたは、コンテナの最後に、反復のような例を管理するためのいくつかの注意が必要です。ノードのデストラクタで

WARNING

私が読んで：

if (mParent) delete mParent; 

これは危険になりますのparentNodeを削除します誰？左か右の子供？