在 Swift 中实现简单树结构的递归生成器

我在内存中有一个基于 XML 文档的简单树结构，我正在尝试编写一个递归生成器来支持SequenceType，但我不知道如何实际做到这一点。

这是我的第一次尝试：

@objc public class XMLNode: NSObject, SequenceType {
    public weak var parentNode: XMLNode?
    public var nodeName: String
    public var attributes: [String: String]
    public var childNodes = [XMLNode]()

    public func generate() -> AnyGenerator<XMLNode> {
        var childGenerator = childNodes.generate()
        var returnedSelf = false

        return anyGenerator {
            let child = childGenerator.next()

            if child != nil {
                // I need to somehow recurse on child here

                return child
            } else if !returnedSelf {
                returnedSelf = true
                return self
            } else {
                return nil
            }
        }
    }
}

Since childNodes是一个数组，我调用它自己的内置generate()函数在子节点上创建生成器并迭代它，然后返回self在最后。问题是它不会在每个孩子身上递归，所以它只会深入一层。我不知道如何以这种方式组合两个生成器。

我很难弄清楚如何做到这一点！制作递归生成器需要做什么？

我不知道生成器本身是否可以递归。 罢工> 威尔·M证明我错了!

这是前序遍历的可能实现，使用堆栈来存储仍需要枚举的子节点：

extension XMLNode : SequenceType {
    public func generate() -> AnyGenerator<XMLNode> {
        var stack : [XMLNode] = [self]
        return anyGenerator {
            if let next = stack.first {
                stack.removeAtIndex(0)
                stack.insertContentsOf(next.childNodes, at: 0)
                return next
            }
            return nil
        }
    }
}

对于层序遍历，替换

stack.insertContentsOf(next.childNodes, at: 0)

by

stack.appendContentsOf(next.childNodes)