4

如果有一棵树，它有一个rootNode，并且它的子节点指向左和右（二叉树），有没有办法像在 Objective-C 2.0 中那样将它转换为快速枚举？所以我们可以做

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

最好不用为内存大小构造 O(n) 对象，而是使用诸如 、 或 的NSMutableArray集合NSSet对象NSDictionary。

顺序并不重要，但它可能会以深度优先顺序出现。

4

3 回答 3

2

当您实现快速枚举时，您不必一次返回所有元素。当然，如果你一次返回一个，你得到的只是快速的枚举语法，而没有太多的性能优势。

您可以在每次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

正如 Jody 和 waldrumpus 所说，你应该遵守NSFastEnumeration. 这将允许您编写：

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

除此之外，正如您所说，还有许多枚举方法，即遍历您的树：首先想到的是深度优先（前序、中序、后序）或广度优先。您可以对树进行子类化并根据需要提供委托方法的不同实现countByEnumeratingWithState:objects:count，或者（更好）具有描述如何遍历树的 typedef 和属性，并在委托方法中对此提出上诉。

于 2012-09-06T14:32:34.107 回答
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 回答