在Swift中为简单的树结构实现递归生成器 [英] Implementing recursive generator for simple tree structure in Swift

问题描述

我在内存中有一个基于XML文档的简单树结构，并且我试图编写一个递归生成器以支持SequenceType，但是我仍然坚持如何实际执行此操作.

I have a simple tree structure in memory based on an XML document and I am trying to write a recursive generator to support SequenceType, but I am stuck on how to actually do this.

这是我的第一次尝试:

@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
            }
        }
    }
}

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

Since childNodes is an array, I'm calling its own built-in generate() function to create a generator on the child nodes and iterating it, and then returning self at the end. The problem is it's not recursing on each child, so it only ever goes one level deep. I can't figure out how to combine two generators in that way.

我很难解决这个问题！我需要做些什么来生成递归生成器?

I'm having a hard time wrapping my head around how to do this! What do I need to do to make a recursive generator?

推荐答案

我不知道生成器本身是否可以递归. M 会证明我错了吗！

这是一个可能的预遍历实现，它为仍需要枚举的子节点使用堆栈:

Here is a possible implementation for a pre-order traversal, using a stack for the child nodes which still have to be enumerated:

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
        }
    }
}

要进行水平顺序遍历，请替换

For a level-order traversal, replace

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

作者

stack.appendContentsOf(next.childNodes)

这篇关于在Swift中为简单的树结构实现递归生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！