10

範囲ベースのforループを使用できるように、バイナリツリー上にイテレータを作成したいと思います。最初にbegin（）関数とend（）関数を実装する必要があることを理解しています。

Beginはおそらくルートを指しているはずです。ただし、仕様によれば、end（）関数は「最後の有効な要素に続く要素」を返します。それはどの要素（ノード）ですか？「無効な」場所を指すことは違法ではないでしょうか。

もう1つはoperator++です。ツリーの「次の」要素を返すための最良の方法は何ですか？このプログラミングを始めるには、アドバイスが必要です。

質問を拡張/拡張したいと思います*。任意のアリティを持つツリーを反復処理したい場合はどうなりますか？各ノードに子のベクトルを持たせ、begin（）が「実際の」ルートを指すようにします。おそらく、unique_ptrをノードに格納するために、イテレータクラス内に（幅優先の）キューを実装する必要がありますよね？次に、キューが空の場合、すべてのノードを通過したことがわかります。したがって、oprator ++（）が呼び出されたときにTreeIterator（nullptr）を返す必要があります。それは意味がありますか？私はそれをできるだけ単純にし、前方反復のみを望んでいます。

*または、新しいスレッドを作成する必要がありますか？

4

3 に答える 3

13

どこbegin()を指すかは、ツリーをトラバースする順序によって異なります。ルートを使用することは、たとえば、木の幅優先探索に適している場合があります。end()は実際にはツリーノード上にありません。この位置にアクセスし、シーケンスの最後に到達したことを示します。ツリーに関連するものを示すかどうかは、サポートする反復の種類によって異なります。順方向の反復のみをサポートする場合は、終了を示すことができます。双方向反復もサポートする場合、終了直前にノードを見つける方法を知る必要があります。

いずれにせよ、ポイントされた場所は実際にはアクセスされておらず、適切なインジケーターが必要です。前方反復の場合、イテレータのみend()がnullを指すイテレータを返すことができ、最後のノードから移動するときに、イテレータのポインタもnullに設定します。2つのポインタを等しく比較すると、が生成さtrueれ、最後に到達したことが示されます。双方向反復をサポートする場合は、前のノードに移動するために使用できるが、値を格納する必要のない、ある種のリンクレコードが必要になります。

順序付けられた関連コンテナ（、、std::map<K, V>などstd:set<V>）は、ある種のツリー（たとえば、赤/黒木）として内部的に実装されます。begin()イテレータは左端のノードから始まり、イテレータend()は右端のノードの後の位置を参照します。は、現在の右側のoperator++()次のノードを見つけるだけです。

  • イテレータが右の子ノードのないノードにある場合、ツリーの左側のブランチを介して親が子に到達するまで、イテレータは親のチェーンに沿って歩きます。
  • 右の子ノードを持つノードにある場合は、子に移動し、この子の左の子のシーケンス（存在する場合）を下って、右のサブツリーで左端の子を見つけます。

明らかに、ツリーを左から右に歩くのではなく、たとえば上から下に歩く場合は、別のアルゴリズムが必要になります。私にとって最も簡単なアプローチは、一枚の紙に木を描き、次のノードに到達する方法を確認することです。

独自のイテレータを使用してデータ構造を実装していない場合は、リストなどの単純なシーケンシャルデータ構造で試してみることをお勧めします。次のノードに到達する方法と、終了に到達するタイミングは非常に明白です。一般的な反復の原則が明確になったら、ツリーを作成するには、ナビゲーションを正しく行うだけです。

于 2012-10-02T03:50:38.850 に答える
11

RBTreeのSGI実装を見てください（これはstd::set/ std::map...コンテナーのベースです）。

http://www.sgi.com/tech/stl/stl_tree.h

begin（）が左端のノードであることがわかります。

end（）は、スーパールートである特別な「空の」ノードヘッダーであることがわかります。つまり、実際のルート（ツリーが空でない場合にのみプリセット）がその子ノードです。

operator ++右の子に移動して、この子の左端のノードを見つけることです。そのような子が存在しない場合は、右端の親ノードの左の親に移動します。この例のように（赤い線はスキップ移動、青い線は終了が反復の指定されたステップです）：

ここに画像の説明を入力してください

SGIからコピーされたコード：

  void _M_increment()
  {
    if (_M_node->_M_right != 0) {
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

ツリーが空の場合、begin()ヘッダーの左端にあるため、ヘッダー自体です。end()ヘッダーでもありbegin() == end()ます。begin() == end()覚えておいてください-あなたの反復スキームは空の木のためにこの条件に一致しなければなりません。

これは非常にスマートな反復スキームのようです。

もちろん、独自のスキームを定義することもできますが、学んだ教訓は、end()目的のために特別なノードを用意することです。

于 2012-10-02T04:53:23.547 に答える
0

ツリーのイテレータは単なるポインタではありませんが、ポインタが含まれている可能性があります。

struct TreeIterator {
  TreeIterator(TreeNode *node_ptr) : node_ptr(node_ptr) { }
  TreeIterator &operator++();
  TreeIterator operator++(int);
  bool operator==(const TreeIterator &) const;

  private:
    TreeNode *node_ptr;
};

TreeIterator begin(const Tree &tree) { ... }
TreeIterator end(const Tree &tree) { ... }

end（）関数に次のような特別なものを返すようにすることができますTreeIterator(nullptr)

開始イテレータが指すものは、必要なトラバーサルのタイプによって異なります。幅優先探索を実行している場合は、ルートから開始するのが理にかなっています。

于 2012-10-02T03:45:08.970 に答える