4

を持つツリーがあり、rootNodeその子ノード (バイナリ ツリー) の左右を指している場合、Objective-C 2.0 のように高速列挙に変換する方法はありますか? だから私たちはできる

for (id node in [tree allNodes]) {
    // do something
}

NSMutableArray、NSSet、などのコレクション オブジェクトを使用して、メモリ サイズの O(n) オブジェクトを構築せずに、できればNSDictionary。

順序は重要ではありませんが、深さ優先の順序になる可能性があります。

4

3 に答える 3

2

高速列挙を実装する場合、一度にすべての要素を返す必要はありません。もちろん、それらを一度に 1 つずつ返すと、高速な列挙構文しか得られず、パフォーマンス上の利点はほとんどありません。

が呼び出されるたびに 1 つの要素をcountByEnumeratingWithState:objects:count返すことも、すべての要素を返すことも、N 個の要素だけを返すこともできます。

たとえば、大きな木があるとします。渡されたスタック バッファとその長さを使用できます。

NSUInteger numItemsToReturn = MIN(100, lengthOfStackBuffer);

numItemsToReturn次に、ツリーの最後まで、またはツリーの最後に到達するまで、ツリーのトラバーサルを続けることができます。

内部インフラストラクチャは countByEnumeratingWithState:objects:count、適切な数の要素を「確認」するまで呼び出しを続けます。

ただし、データの一部のみを返す場合はstate、次に再開する場所がわかるように、 に情報を保存する必要があることに注意してください。それextraがそのためです。

編集

元の投稿に対するコメントを見ました...高速列挙をサポートしたい場合は、上記のように非常に簡単です。

ただし、ツリーをたどって何かをしたいだけの場合は、列挙 API を検討することをお勧めします。例えば：

-(void)enumerateWithOptions:(MyTreeEnumerationOptions)options
                 usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop)block {
    // In here, you can use the options to determine if you are doing
    // pre/post depth first search, breadth-first, reverse, even concurrent.
    // You also provide an easy way to communicate to the caller not only the
    // object at this node, but the tree-depth of this node, whether it is a
    // leaf, and anything else you want to communicate.
}

その後、ユーザーは次を呼び出すことができます。

[tree enumerateWithOptions:PreOrderDepthFirst
                usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop) {
    // Execute whatever code you want with this object...
    // Set *stop = YES to abort the enumeration.
}];
于 2012-09-06T14:24:34.603 に答える
1

ツリーを複数の方法 (前、中、後) でトラバースする場合はNSEnumerator、単に に準拠するのではなく、独自のサブクラスを作成することも検討してくださいNSFastEnumeration。

したがって、ツリーをトラバースする方法を知っている NSPreorderEnumerator、NSInorderEnumerator、および NSPostOrderEnumerator サブクラスを作成します。

次に、ツリー用に作成された新しい列挙子を返すことによって、ツリー オブジェクトが-preorderEnumerator,に応答するようにします。-inorderEnumerator-postorderEnumerator

その後、次のことができます

for(id node in [tree preorderEnumerator]) {
    // do stuff
}

for(id node in [tree postorderEnumerator]) {
    // do stuff
}

NSArrayと同様-reverseObjectEnumeratorのことを行います。これにより、逆方向にループできます。

于 2012-09-06T14:46:09.297 に答える
1

Jody と waldrumpus が言うように、 に準拠する必要がありますNSFastEnumeration。これにより、次のように記述できます。

for (id node in tree) {
    // do something
}

これに加えて、あなたが言うように、列挙する方法、つまりツリーをトラバースする方法がいくつかあります: 深さ優先 (事前順、順序順、後順) または幅優先が思い浮かびます。ツリーをサブクラス化し、適切にデリゲート メソッドのさまざまな実装を提供するcountByEnumeratingWithState:objects:countか、(より良い) ツリーをトラバースする方法を説明する typedef とプロパティを用意し、デリゲート メソッドでこれにアピールすることができます。

于 2012-09-06T14:32:34.107 に答える