1

私は2つの理由でバイナリ検索ツリーテンプレートを書いています-C++を学ぶことと、最も一般的なアルゴリズムとデータ構造を学ぶことです。
それで、ここに質問があります-私がイテレータを実装したい限り、ツリーがどこで終わるかについての厳密な定義はないように私には思えます。あなたの提案は何ですか？どうすればよいですか？

4

7 に答える 7

9

ツリーの場合、ツリーをトラバースする、つまりノードを列挙するための標準があります。プリオーダー トラバーサル、インオーダー トラバーサル、ポストオーダー トラバーサルです。これらすべてをここで説明するのではなく、次の URL にリダイレクトします。http://en.wikipedia.org/wiki/Tree_traversal。概念は主に二分木に適用されますが、ケースを追加することで任意のツリーにアイデアを拡張できます: 事実上、ノードを処理してから再帰する、再帰してノードを処理する、すべての子を処理してからそれぞれに再帰する...など。私が知っているこのアプローチの標準的な分類はありません。

于 2009-07-30T15:49:59.967 に答える
6

イテレータを記述するときは、明確にしておく必要があります。データ構造のイテレータは、アイテムの線形シーケンスとしてコレクションへのアクセスを提供します。配列、リスト、キューなどの特定のコレクションは、線形シーケンスとして扱われることと自然に互換性があります。他のタイプのコレクション (ツリー、辞書、グラフ) は、線形リストとして単純に解釈されるとは限りません。実際、複数の解釈が一般的に有効です。

ツリーのようなコレクションの反復子を作成するときに実際に行うことは、次の懸念事項に対処することです。

  1. コレクションの反復はどこから始まりますか (ルート? 葉?)
  2. 反復は次の要素 (中置? 後置? 接尾辞? 幅?) にどのように進みますか?
  3. 反復はいつ終了しますか (葉? ルート? 最終ノード?)

どちらを選択する場合でも、イテレータがどのようにノードにアクセスして発行するかを明確にするために、イテレータに名前を付ける方法 (および文書化する方法) を明確にする必要があります。

サポートするさまざまな種類の走査に対して、複数の反復子を作成する必要がある場合があります。ここには、ツリー トラバーサル モデルについて論じている優れた記事がいくつかあります。

于 2009-07-30T15:54:57.743 に答える
2

「厳密」とは、すべてを包括する単一の定義を意味する場合、その通りです。定義はありません。

しかし、ツリーの「終了」は非常に明確に定義されていますが、選択しているトラバーサル方法によって異なります。

  • inorder (または対称) トラバーサルを行う場合、最も右の要素は になりますend。
  • 先行順 (または深さ優先) では、右端の要素はendなどになります。
  • ポストオーダーでは、ルート要素はendなどになります。

最も一般的なツリー トラバーサルメソッド。

于 2009-07-30T15:51:58.373 に答える
1

イテレータの定義が少し間違っています。イテレータは、最初から最後までも、前から後ろにも移動しません。代わりに、その構造のすべてのメンバーに渡ります。

順序付けられた構造、つまり配列、連結リストなどの反復を要求すると、(通常) 順序どおりにメンバーが返されます。

セットなどの順序付けされていないアイテムの場合、セット イテレータが指定した順序でアイテムを取得しますが、配列の場合と同様に、一度に 1 つずつすべてを取得します。 -イテレータ。

木に関しては、他の人がすでに言及しています: それらは完全な順序の明確に定義された概念を持っています。

于 2009-07-30T16:12:57.487 に答える
0

ツリーで何をしたいかによって異なります。たとえば、幅優先検索または深さ優先検索 (または両方) のイテレータを使用するとよいでしょう。

木を精練する特定の方法がある場合、実際には始まりと終わりがあります。リストやセットの線形関係ほど明白ではありませんが、何らかの順序付けを課したい場合はそこにあります。

于 2009-07-30T15:52:47.590 に答える
0

クラスのユーザーは、状況に応じてさまざまな方法ですべての要素を簡単に移動できるため、特にそのような場合に意味があります。それらがなければ、ユーザーは複雑な、通常は再帰的な方法を自分で書く必要があります。for(i=0;i

于 2009-07-30T15:54:11.393 に答える
-2

私はイテレータでより抽象的な方法で考えます。イテレータ パターンには、開始または終了があると実際に言っているものは何もありません。では、なぜそのビジョンに制約されるのでしょうか。次の要素のみに関係する反復子を想像できます。それだけです。つまり、最初からコレクションの拡張がわからない、いつか終了するかどうかわからない、またはすべてのコレクションを持っていないという状況に (特に大量処理で) 直面しました。メモリにロードされた要素であり、気にしません。次の要素を取得することだけに関心があります。これらの実装の 1 つでは、次の要素メソッドが呼び出された直後に次のノードが作成されます。私たちは心を開いて、すべての数のコレクションのような無限のコレクション (最終的にコレクションは数学的集合の一種です) について考えることができます。すべての乱数のコレクション。実際にすべての要素をメモリに保持する必要はありません (これは、無限のコレクションでは明らかです)。もちろん、これは実用的な例ではありませんが、Iterator のユーザーは、コレクションの実際の構造や拡張に依存する必要はないということを伝えたいと思います。ちょうど私に次を与えてください（あなたがそれを持っているなら）。

于 2014-05-02T20:21:03.693 に答える