ruby - 实现树迭代器

Question

我创建了一个非常简单的节点类，其中包含一个名称和一个节点数组。我还创建了一个带有 next 方法的迭代器类，该方法帮助我在每个节点和子节点上进行迭代。我需要编写下一个方法，但我不知道最好的方法是什么。

class Node

  def initialize(name, nodes
    @name = name
    @nodes = nodes
  end
end

class Iterator
  def initialize(node)
    @node = node
  end

  def next
    ???
  end
end

例子：

z = Node.new("z", [])
b = Node.new("b", [z])    
c = Node.new("c", [])
parent = Node.new("a", [b, c]) 

iterator = Iterator.new(parent)
str = ''
next = iterator.next
while next do
 str += next.name
 next = iterator.next
end

str 应该等于“abzc”

有人可以帮我吗？

Answer 1

如果我可以建议一种更惯用的方法：

class Node

  attr_accessor :name, :children

  def initialize(name, children = [ ])
    @name = name
    @children = children
  end

  def traverse(&block)
    yield self
    @children.each { |child| child.traverse(&block) }
  end

end

z = Node.new("z")
b = Node.new("b", [z])
c = Node.new("c")
parent = Node.new("a", [b, c])

str = ''
parent.traverse { |node| str += node.name }
puts str

这比 btilly 的解决方案（这也是正确的）有一个好处，因为它不会增殖 Iterator 对象并占用内存 - 实际上 Iterator 从实现中消失了（同时仍然保留对每个节点执行操作的能力连续）。这更惯用；更红宝石风格。

Answer 2

在您的迭代器中，如果节点有任何子节点，则 next 将是其中的第一个。如果没有，那么您需要“备份”到您跳过的最后一个兄弟姐妹。这意味着您需要跟踪已跳过的兄弟姐妹，以便您可以返回到它们。

Answer 3

通过执行以下操作，我已经能够解决我的问题。但是我不喜欢这种方法的是我在初始化期间而不是在下一个方法中遍历节点......

class Iterator

  def initialize(node)
    @node   = node
    @index  = -1
    @list   = []

    traverse(@node)
  end

  def next
    @index += 1
    @list[@index]
  end

  private
  def traverse(root)
    @list[@list.size] = root
    if root.nodes
      for n in root.nodes do
        traverse(n)
      end
    end  
  end

end

Answer 4

这是一些运行代码，演示了我认为您正在寻找的内容。

class Node
  attr_accessor :name, :nodes

  def initialize(name, nodes)
    @name = name
    @nodes = nodes
  end
end

class Iterator
  def initialize(node)
    @node = node
  end

  def each_node
    yield @node
    for node in @node.nodes do
      iterator = Iterator.new(node)
      iterator.each_node {|next_node|
        yield next_node
      }
    end
  end
end

z = Node.new("z", [])
b = Node.new("b", [z])
c = Node.new("c", [])
parent = Node.new("a", [b, c])

iterator = Iterator.new(parent)
str = ''
iterator.each_node {|node|
  str += node.name
}
puts str