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

发布时间：2020-12-14 04:37:19 所属栏目：百科来源：网络整理

导读：我在内存中有一个基于 XML文档的简单树结构,我正在尝试编写一个递归生成器来支持SequenceType,但我仍然坚持如何实际执行此操作. 这是我的第一次尝试： @objc public class XMLNode: NSObject,SequenceType { public weak var parentNode: XMLNode? public va

我在内存中有一个基于 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
            }
        }
    }
}

由于childNodes是一个数组,我正在调用它自己的内置generate()函数来在子节点上创建一个生成器并迭代它,然后在结束时返回self.问题是它并不是每个孩子的递归,所以它只会达到一个深度.我无法弄清楚如何以这种方式组合两个发电机.

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

解决方法

我不知道发电机本身是否可以递归.
?请问M proved me wrong！

这是一个可能的预执行遍历实现,使用堆栈为子节点仍然必须枚举：

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)

通过

stack.appendContentsOf(next.childNodes)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!