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

Question

我在内存中有一个基于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。问题是它没有递归每个子节点，所以它只深入了一层。我无法想出如何将两个生成器组合起来。

我很难理解如何做到这一点！我需要做什么来创建一个递归生成器？

- devios1

---

childNodes 是如何定义的？return self 中的 self 是什么？也许您可以提供一个（简化的）自包含的树结构示例，这将更容易找到（和测试）可能的解决方案。 - Martin R

你想要进行什么类型的树遍历？ - Will M.

基本上是深度优先的前序或后序遍历，但这并不是非常重要。 - devios1

你如何将此内容填充到重复的UITableView中？ - Number1

Answer 1

我不知道一个生成器本身是否可以递归。 Will 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)

- Martin R

---

这对于预订非常有效，比我尝试的要简单得多！干杯！ - devios1

关于你的第一行，我认为我的答案是一个递归生成器，但我并不100%确信我没有作弊，使它不是真正的递归。 - Will M.

@WillM.：我认为你是对的。我花了一些时间才理解它 :) - Martin R

Answer 2

这是一个递归的后序生成器。虽然我不建议实际使用它。 @MartinR的答案似乎更实用。

 public func generate() -> AnyGenerator<XMLNode> {
    var childGenerator:AnyGenerator<XMLNode>?
    var childArrayGenerator:IndexingGenerator<[XMLNode]>? = self.childNodes.generate()
    var returnedSelf = false

    return anyGenerator {
        if let next = childGenerator?.next() {
            return next
        }
        if let child = childArrayGenerator?.next() {
            childGenerator = child.generate()
            return childGenerator?.next()

        } else if !returnedSelf {

            returnedSelf = true
            return self

        } else {

            return nil
        }
    }
}

- Will M.

---

我实际上刚刚成功地实现了一个类似的程序！但我认为你是对的，@MartinR的堆栈解决方案似乎更简单。 - devios1

Answer 3

虽然Martin的答案更加简洁，但它的缺点是使用了大量的数组/插入操作，并且在懒序列操作中不太可用。这种替代方案应该适用于这些环境，我已经在UIView层次结构中使用了类似的东西。

public typealias Generator = AnyGenerator<XMLNode>

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

    return anyGenerator {
        if !returnedSelf {
            returnedSelf = true
            return self
        }

        if let subGenerator = subGenerator,
            let next = subGenerator.next() {
                return next
        }

        if let child = childGenerator.next() {
            subGenerator = child.generate()
            return subGenerator!.next()
        }

        return nil
    }
}

请注意，这是预订迭代，您可以将if !returnedSelf块移动到后序位置。

- David Berry

---

关于数组插入的观点很好，这样做的好处是可以轻松地在前序和后序之间进行转换，就像@WillM.的答案一样。 - devios1